EPS.AC es el equipo encargado de preparar los problemas de este concurso. Sus miembros son Colin, Claris y Little_Sheep_Yawn.
Han preparado $n$ problemas candidatos para este concurso. Cada miembro ordena los $n$ problemas del más fácil al más difícil según su propio criterio. Para equilibrar la dificultad del concurso y distinguir a los participantes de distintos niveles, quieren dividir estos problemas en niveles de dificultad, ordenados del más fácil al más difícil. Cada problema debe pertenecer exactamente a un nivel. Los problemas de un mismo nivel no están ordenados por dificultad, y cada nivel debe contener al menos un problema.
Ordena los niveles de izquierda a derecha, del más fácil al más difícil. Para una frontera entre dos niveles consecutivos, el lado izquierdo contiene todos los problemas de los niveles anteriores a ella, y el lado derecho contiene todos los problemas de los niveles posteriores a ella. Un miembro apoya esta frontera si todos los problemas de su lado izquierdo aparecen antes que todos los problemas de su lado derecho en la clasificación de ese miembro.
Una división en niveles es válida si cada frontera cuenta con el apoyo de al menos dos miembros. Las distintas fronteras pueden tener distintos partidarios.
Un mayor número de niveles de dificultad significa una mejor preparación de los problemas. Para ayudarles a crear un buen concurso, encuentra el máximo número posible de niveles.
Entrada
La entrada contiene varios casos de prueba. La primera línea contiene un entero $t$ ($1 \le t \le 2 \times 10^5$), el número de casos de prueba.
Para cada caso de prueba:
- La primera línea contiene un entero $n$ ($1 \le n \le 2 \times 10^5$).
- Cada una de las tres líneas siguientes contiene una permutación de $1,2,\ldots,n$, que da las clasificaciones de Colin, Claris y Little_Sheep_Yawn, respectivamente.
Se garantiza que la suma de $n$ de todos los casos de prueba es como máximo $2 \times 10^5$.
Salida
Para cada caso de prueba, imprime el máximo número posible de niveles.
Ejemplos
Entrada 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
Salida 1
3 4 1
Nota
En el primer caso de prueba, los problemas pueden dividirse en tres niveles $\{1,2\}$, $\{3,4\}$, $\{5,6\}$, enumerados del más fácil al más difícil. Colin y Claris apoyan la primera frontera, mientras que Claris y Little_Sheep_Yawn apoyan la segunda. Esta división es óptima.
En el segundo caso de prueba, cada uno de los cuatro problemas puede formar su propio nivel, ordenados del más fácil al más difícil como $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$. Las tres fronteras cuentan con el apoyo de Colin y Claris, de Claris y Little_Sheep_Yawn, y de Colin y Little_Sheep_Yawn, respectivamente.
En el tercer caso de prueba, ninguna frontera es válida, por lo que todos los problemas deben colocarse en un único nivel.