0

Longest Common Prime Subsequence

Difficulty: MEDIUM

Problem Statement
Suggest Edit

Ninja got a very long summer vacation. Being very bored and tired about it, he indulges himself in solving some puzzles.

He encountered a problem in which he was given two arrays of integers of length ‘N’ and ‘M’ respectively and he had to find the longest common prime subsequence.

Ninja wants help in solving the problem as he is not getting the approach so he approaches you as he knows that you are very good at building logics. Help Ninja!

Note:

A subsequence is a sequence that can be derived from another sequence by zero or more elements, without changing the order of the remaining elements.

Input format :

The first line of input contains an integer ‘T’, which denotes the number of test cases. Then each test case follows.

The first line of each test case contains two separated integers ‘N’ and ‘M’ denoting the length of two arrays.

The second line of each test case contains space-separated ‘N’ integers representing elements of the first array.

The third line of each test case contains space-separated ‘M’ integers representing elements of the second array.
Output format :
For each test case print an integer representing the length of the longest prime subsequence of the two arrays.
Note:
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N, M <= 5 * (10 ^ 2)
1 <= arr1[i], arr2[i] <= 300

Where arr1[i], arr2[i] represents ith element of arr1 and arr2 respectively.

Time Limit: 1 sec.
Sample Input 1 :
2
5 3
1 2 3 4 5
1 2 3
7 7
5 7 8 4 6 9 3
1 5 4 7 8 9 3 
Sample Output 1 :
2
3

Explanation for Sample Test 1:

Test Case1 :
Longest prime subsequence obtained is of length 2 containing 2 and 3 from the two given arrays.

Test Case 2:
Longest prime subsequence obtained is of length 3 containing 5, 7 and 3 from the two given arrays.
Sample Input 2 :
2
6 7
5 2 1 7 8 9
1 2 3 4 5 6 7
8 4
4 7 8 5 1 2 3 6 
8 4 7 5 
Sample Output 1 :
2
2
Reset Code
Full screen
copy-code
Console