C. LCIS
time limit per test
3 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two permutations $$$a$$$ and $$$b$$$ of length $$$n$$$. Determine their (LCIS) – the length of their longest common increasing subsequence.

Input

The first line contains integer $$$T$$$ the number of test cases.

For each test case:

The first line of each test case contains the integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots a_n$$$ ($$$1\leq a_i \leq n$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots b_n$$$ ($$$1\leq b_i \leq n$$$).

Output

For each test case output one line containing the answer.

Example
Input
4
5
3 2 1 4 5
1 2 3 4 5
8
5 2 4 3 1 6 7 8
1 4 2 3 5 7 6 8
6
6 5 4 3 2 1
1 2 3 4 5 6
5
2 5 4 3 1
5 2 4 3 1
Output
3
4
1
2
Note

In the first test, the possible answers are: $$$2, 4, 5$$$, or $$$3, 4, 5$$$

In the second test, one of the possible answers is: $$$2, 3, 6, 8$$$

In the third test, any subsequence with size one can be an answer.

In the third test, one of the possible answers is: $$$2, 4$$$