3575: K Multiple Longest Commom Subsequence--2018HBCPC E

KK has two sequences, A and B, and wants to find the k multiple longest common subsequence.A sequence S is a k multiple common subsequence of A and B if and only if it satisfies the following conditions:

1) S is a subsequence of A and is a subsequence of B. (A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.)

2) The length of S is t×k where t is a nonnegative integer. The first element of S is S[1]. If we divide the sequence into t groups with the ith group containing S[(i-1)×k+j](1<=j<=k), for every element g, it shares the same value with other elements that are in the same group which g belongs to.

For example, [1,1,2,2] is a double common subsequence of [1,2,3,1,2,3,2] and [1,3,1,2,2]. KK wants to know the maximum length of such sequence.

The first line is an integer T, denoting the number of test cases.

For each test case, the first line are three integers k , n, m, denoting the kind of subsequence, the length of A and the length of B.

The second line are n integers A₁~A_n, representing the elements of A.

The third line are m integers B₁~B_m, representing the elements of B.

1<=T<=10 , 1<=k,n,m<=10^3, 1<=A_i,B_i<=10³.

For each test case, output a line with the maximum length of k multiple common subsequence.

3
1 4 5
1 2 3 4
4 1 3 2 4
2 8 7
1 1 2 2 3 3 4 4
1 2 3 1 2 3 3
3 9 9
1 1 1 2 2 2 3 3 3
1 2 3 1 2 3 1 2 3

3
4
3