시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 1 | 1 | 1 | 100.000% |
Chiaki has two sequences $a_1,a_2,\ldots,a_n$ and $b_1,b_2,\ldots,b_m$. She would like to find their longest common subsequence $c_1,c_2,\ldots,c_k$ such that $c_1 \le c_2 \le \ldots \le c_k$.
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 two integers $n$ and $m$ ($1 \le n, m \le 10^6$): the lengths of two sequences.
The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 3$).
The third line contains $m$ integers $b_1,b_2,\ldots,b_m$ ($1 \le b_i \le 3$).
It is guaranteed that the sum of $\max\{n,m\}$ in all test cases does not exceed $10^6$.
For each test case, output a single integer $k$: the length of the longest common subsequence $c_1,c_2,\ldots,c_k$ such that $c_1 \le c_2 \le \ldots \le c_k$.
3 3 3 1 2 3 1 2 3 3 3 1 1 1 1 1 2 3 3 1 3 2 1 2 3
3 2 2