LCS

You are given two sequence $\{a_1, a_2, ..., a_n\}$ and $\{b_1,b_2, ... ,b_n\}$. Both sequences are permutation of $\{1,2,...,n\}$. You are going to find another permutation $\{p_1,p_2,...,p_n\}$ such that the length of LCS (longest common subsequence) of $\{a_{p_1},a_{p_2},...,a_{p_n}\}$ and $\{b_{p_1},b_{p_2},...,b_{p_n}\}$ is maximum.

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n (1 \le n \le 10^5)$ - the length of the permutation. The second line contains $n$ integers $a_1,a_2,...,a_n$. The third line contains $n$ integers $b_1,b_2,...,b_n$.

The sum of $n$ in the test cases will not exceed $2 \times 10^6$.

For each test case, output the maximum length of LCS.

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

2
4

BestCoder Round #58 (div.2)