EPS.AC는 이 대회의 출제 팀이다. 팀원은 Colin, Claris, Little_Sheep_Yawn이다.

이들은 이 대회를 위해 $n$개의 후보 문제를 준비했다. 각 팀원은 자신의 판단에 따라 $n$개의 문제를 가장 쉬운 것부터 가장 어려운 것까지 순서대로 나열한다. 대회의 난이도를 균형 있게 조절하고 서로 다른 수준의 참가자들을 구별하기 위해, 이들은 문제들을 가장 쉬운 것부터 가장 어려운 것까지 순서가 있는 난이도 등급으로 나누려고 한다. 모든 문제는 정확히 하나의 등급에 속해야 한다. 같은 등급 안의 문제들에는 난이도 순서를 정하지 않으며, 각 등급에는 적어도 하나의 문제가 있어야 한다.

등급들을 가장 쉬운 것부터 가장 어려운 것까지 왼쪽에서 오른쪽으로 나열하자. 연속한 두 등급 사이의 경계에 대해, 왼쪽에는 그 경계보다 앞에 있는 등급들의 모든 문제가, 오른쪽에는 그 경계보다 뒤에 있는 등급들의 모든 문제가 포함된다. 한 팀원의 순서에서 경계 왼쪽의 모든 문제가 오른쪽의 모든 문제보다 앞에 나타나면, 그 팀원은 이 경계를 지지한다.

모든 경계가 적어도 두 팀원의 지지를 받으면 등급 분할은 유효하다. 서로 다른 경계는 서로 다른 팀원들의 지지를 받을 수 있다.

난이도 등급이 많을수록 더 좋은 출제가 된다. 이들이 좋은 대회를 만들 수 있도록 가능한 등급 수의 최댓값을 구하여라.

입력

입력은 여러 테스트 케이스로 이루어진다. 첫 번째 줄에는 테스트 케이스의 수인 정수 $t$ ($1 \le t \le 2 \times 10^5$)가 주어진다.

각 테스트 케이스에 대해:

• 첫 번째 줄에는 정수 $n$ ($1 \le n \le 2 \times 10^5$)이 주어진다.
• 다음 세 줄 각각에는 $1, 2, \ldots, n$의 순열이 주어지며, 각각 Colin, Claris, Little_Sheep_Yawn이 정한 순서를 나타낸다.

모든 테스트 케이스에 대한 $n$의 합은 $2 \times 10^5$ 이하임이 보장된다.

출력

각 테스트 케이스에 대해 가능한 등급 수의 최댓값을 출력한다.

예제

입력 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

출력 1

3
4
1

참고

첫 번째 테스트 케이스에서는 문제들을 가장 쉬운 것부터 가장 어려운 것까지 $\{1,2\}$, $\{3,4\}$, $\{5,6\}$의 세 등급으로 나눌 수 있다. Colin과 Claris는 첫 번째 경계를 지지하고, Claris와 Little_Sheep_Yawn은 두 번째 경계를 지지한다. 이 분할은 최적이다.

두 번째 테스트 케이스에서는 네 문제 각각이 하나의 등급을 이루어, 가장 쉬운 것부터 가장 어려운 것까지 $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$로 나열될 수 있다. 세 경계는 각각 Colin과 Claris, Claris와 Little_Sheep_Yawn, Colin과 Little_Sheep_Yawn의 지지를 받는다.

세 번째 테스트 케이스에서는 유효한 경계가 없으므로 모든 문제를 하나의 등급에 넣어야 한다.