Busy Beaver está decorando un árbol de Navidad, pero tiene algunas preferencias extrañas sobre qué colores usar.

Considera una coloración de los vértices de un árbol, usando dos colores: rojo y verde.

En una coloración, llamamos a una componente conexa de vértices verdes genial si a lo sumo dos vértices rojos son adyacentes a dicha componente. Para un árbol $t$, sea $f(t)$ el número máximo de componentes geniales en cualquier coloración de $t$.

Existe un árbol $t$, que inicialmente contiene solo un único vértice, denotado como vértice $1$. Realiza $N$ consultas; en la $i$-ésima consulta, añade un vértice hoja adjuntándolo al vértice $a_i$. Hay dos tipos de casos de prueba, dependiendo de una variable $X \in \{0, 1\}$:

• Si $X = 0$, imprime $f(t)$ después de que todas las consultas se hayan completado.
• Si $X = 1$, imprime $f(t)$ después de cada consulta.

Entrada

Hay múltiples casos de prueba. El archivo de entrada comienza con $T$ y $X$ ($1 \le T \le 4\cdot 10^4$, $X \in \{0, 1\}$), el número de casos de prueba y el tipo de prueba respectivamente.

La primera línea de cada caso de prueba contiene un entero $N$ ($1 \le N \le 2 \cdot 10^5$).

La segunda línea contiene $N$ enteros $a_1, \dots, a_N$ ($1 \le a_i \le i$).

Se garantiza que la suma de $N$ sobre todos los casos de prueba no excede $4 \cdot 10^5$.

Salida

Si $X = 0$, entonces para cada caso de prueba, imprime $f(t)$ para el árbol final en una sola línea.

Si $X = 1$, entonces para cada caso de prueba, imprime $N$ líneas, donde la $i$-ésima línea es el valor de $f(t)$ después de la $i$-ésima consulta.

Subtareas

• ($25$ puntos) $X = 0$.
• ($30$ puntos) Cada $a_i$ se elige uniformemente al azar de $[1, i]$.
• ($45$ puntos) Sin restricciones adicionales.

Ejemplos

Entrada 1

2 0
4
1 2 3 3
8
1 2 3 2 3 6 5 7

Salida 1

3
5

Entrada 2

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

Salida 2

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

Nota

Explicación del ejemplo 1

Para el primer caso de prueba, podemos colorear los vértices $1$, $2$, $4$ y $5$ de verde (nótese que hay $N + 1 = 5$ vértices ya que hay un vértice al principio). Entonces $\{1, 2\}$, $\{4\}$ y $\{5\}$ son componentes geniales.

Para el segundo caso de prueba, podemos colorear los vértices $1$, $4$, $5$, $6$, $8$ y $9$ de verde. Entonces $\{1\}$, $\{4\}$, $\{5, 8\}$, $\{6\}$ y $\{9\}$ son componentes geniales.

Explicación del ejemplo 2

Este ejemplo tiene los mismos árboles que el primero, pero es de tipo $X = 1$.