EPS.AC is the problem-setting team for this contest. Its members are Colin, Claris, and Little_Sheep_Yawn.

They have prepared $n$ candidate problems for this contest. Each member ranks the $n$ problems from easiest to hardest according to their own judgment. To balance the contest’s difficulty and distinguish contestants of different levels, they want to divide these problems into difficulty tiers, ordered from easiest to hardest. Every problem must belong to exactly one tier. Problems within the same tier are not ordered by difficulty, and each tier must contain at least one problem.

Arrange the tiers from left to right, from easiest to hardest. For a boundary between two consecutive tiers, the left side contains all problems in the tiers before it, and the right side contains all problems in the tiers after it. A member supports this boundary if every problem on its left appears before every problem on its right in that member’s ranking.

A division into tiers is valid if every boundary has the support of at least two members. Different boundaries may have different supporters.

More difficulty tiers mean better problem setting. To help them create a good contest, find the maximum possible number of tiers.

Input

The input contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 2 \times 10^5$), the number of test cases.

For each test case:

• The first line contains an integer $n$ ($1 \le n \le 2 \times 10^5$).

• Each of the next three lines contains a permutation of $1, 2, \ldots, n$, giving the rankings of Colin, Claris, and Little_Sheep_Yawn, respectively.

It is guaranteed that the sum of $n$ over all test cases is at most $2 \times 10^5$.

Output

For each test case, print the maximum possible number of tiers.

Examples

Input 1

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

Output 1

3
4
1

Note

In the first test case, the problems can be divided into three tiers $\{1, 2\}, \{3, 4\}, \{5, 6\}$, listed from easiest to hardest. Colin and Claris support the first boundary, while Claris and Little_Sheep_Yawn support the second. This division is optimal.

In the second test case, each of the four problems can form its own tier, ordered from easiest to hardest as $\{1\}, \{2\}, \{3\}, \{4\}$. The three boundaries are supported by Colin and Claris, by Claris and Little_Sheep_Yawn, and by Colin and Little_Sheep_Yawn, respectively.

In the third test case, no boundary is valid, so all problems must be placed in a single tier.