LCS

Time Limit: 2 Seconds    Memory Limit: 32768 KB

According to Wikipedia:

 

 The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring problem: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. The longest common subsequence problem is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in bioinformatics. It is also widely used by revision control systems such as Git for reconciling multiple changes made to a revision-controlled collection of files.

   In simpler terms, for two sequence of elements, if you can make the two sequences the same by deleting some elements from them, the remaining sequence is called "common sub-sequence". And the longest common sub-sequence of the two sequences, obviously, is called "LCS".

  Now, you are given two sequences of integers and you can permute the elements of each sequence. Out of all the permutations, what is the maximum LCS of the two sequences?

Input

  The first line contains the number of test cases T (1 ≤ M ≤ 64).

  For each test, the first line contains two integers M (0 < M < 10000) and N (0 < N < 10000), the length of each sequence. Next two lines, contain M and N integers respectively, which are the numbers in the two sequences.

  The elements of the sequences are 32-bit signed integers.

Output

  For each test, print one integer in one line, the maximum length of the LCS of all the arrangements of the two sequences.

 

Sample Input

2
2 2
1 2
2 1
4 5
2 3 4 2
2 4 8 4 2

Sample Output

2
3

Submit

Source: 15th Iran Nationwide Internet Contest