Migrated from Lutece 243 Longest Common Increasing Subsequence

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

You should have been familiar with the LCS(Longest Common Subsequence) and LIS(Longest Increasing Subsequence problem. Now, here is a challenge for you to solve the combined problem LCIS.

We call sequence $S$ (with length $M$) is a subsequence of $A$ (with length $N$) if there exist $1 \leq i_1 < i_2 < \cdots < i_M \leq N$ so that $S(1)=A_{i1}, S(2)=A_{i2}, \cdots ,S(M)=A_{iM}$

We call sequence $S$ is a common increasing subsequence of $A$ and $B$ if:

1. $S$ is a subsequence of both $A$ and $B$;
2. $S$ is strictly increasing, which means $S_i<S_{i+1}$($1\leq i <M$)

Input

In the first line is one integer $T$($T\leq 10$).

$T$ cases follow. In each case you will be given two number sequence $A$ and $B$.

On the first line are two integers $LA$ and $LB$ representing the length of $A$ and $B$.

One the second line are $LA$ integers. The $i_{th}$ integer is $A_i$.

One the third line are $LB$ integers. The $i_{th}$ integer is $B_i$.

($1\leq LA,LB\leq 1000$ , $1\leq A_i,B_i\leq 2^{31}-1$).

Output

For each case print one line with an integer $L$ standing for the length of the longest common increasing subsequence of $A$ and $B$.

Samples

3
6 5
1 3 2 3 4 5
1 2 3 4 5
5 5
5 4 3 2 1
5 4 3 2 1
3 3
1 1 1
1 1 1

5
1
1

Resources

StephYDX