Descripción

Hay $n$ Mahou Shoujo sentadas en un círculo, numeradas en sentido horario del 1 al $n$. Entre ellas, algunas son en realidad Majo.

Durante los siguientes $n-3$ días, ocurren los siguientes eventos uno por uno: Por la noche, exactamente una Majo se despierta y mata a la primera Mahou Shoujo viva a su izquierda o derecha (esta persona también podría ser una Majo). Por la mañana, todos se despiertan y descubren a la Mahou Shoujo muerta.

Kamome, como jueza de las Mahou Shoujo, necesita encontrar, después de cada mañana en que se descubre una Mahou Shoujo muerta, el número mínimo de Majo que podrían haber estado presentes el primer día.

Picture 1: The Judgement

Entrada

Cada caso de prueba contiene múltiples casos de prueba. La primera línea contiene un entero $t$ ($1 \le t \le 10^5$), que indica el número de casos de prueba. La descripción de los casos de prueba sigue.

La primera línea contiene dos enteros $n$ ($4 \le n \le 2 \times 10^5$, $1 < \sum n \le 10^6$), que indica el número de Mahou Shoujo.

La segunda línea contiene $n-3$ enteros $p_i$ ($1 \le p_i \le n$, $p_i \ne p_j$ para $1 < i < j < n-3$), indicando la Mahou Shoujo que murió el $i$-ésimo día.

Salida

Para cada caso de prueba, imprime una línea que contenga $n-3$ enteros, indicando el número mínimo de Majo que podrían haber estado presentes el primer día después de descubrir a la Mahou Shoujo muerta el $i$-ésimo día.

Ejemplos

Entrada 1

5
5
1 2
6
2 1 3
9
1 2 3 4 5 6
10
1 3 5 7 9 2 4
10
2 5 1 8 10 9 4

Salida 1

1 1 1 1 1
1 1 2 2 3 3 3
1 2 2 3 3 3 3

Nota

Para el segundo caso de prueba, en el tercer día, al menos 2 Majo podrían haber estado presentes el primer día. Un ejemplo posible es que 3 y 4 sean las Majo, donde 3 mata a 2 el primer día, 3 mata a 1 el segundo día y 4 mata a 3 el tercer día.

Picture 2: A possible example