Busy Beaver décore un sapin de Noël, mais il a des préférences étranges concernant les couleurs à utiliser.

Considérons une coloration des sommets d'un arbre, utilisant deux couleurs : rouge et vert.

Dans une coloration, on appelle une composante connexe de sommets verts cool si au plus deux sommets rouges sont adjacents à cette composante. Pour un arbre $t$, soit $f(t)$ le nombre maximum de composantes cool dans n'importe quelle coloration de $t$.

Il existe un arbre $t$, contenant initialement un seul sommet, noté sommet $1$. Effectuez $N$ requêtes ; lors de la $i^{\text{ème}}$ requête, ajoutez un sommet feuille en le rattachant au sommet $a_i$. Il existe deux types de cas de test, selon une variable $X \in \{0, 1\}$ :

• Si $X = 0$, affichez $f(t)$ après que toutes les requêtes ont été effectuées.
• Si $X = 1$, affichez $f(t)$ après chaque requête.

Entrée

Il y a plusieurs cas de test. Le fichier d'entrée commence par $T$ et $X$ ($1 \le T \le 4\cdot 10^4$, $X \in \{0, 1\}$), le nombre de cas de test et le type de test respectivement.

La première ligne de chaque cas de test contient un entier $N$ ($1 \le N \le 2 \cdot 10^5$).

La deuxième ligne contient $N$ entiers $a_1, \dots, a_N$ ($1 \le a_i \le i$).

Il est garanti que la somme des $N$ sur tous les cas de test ne dépasse pas $4 \cdot 10^5$.

Sortie

Si $X = 0$, alors pour chaque cas de test, affichez $f(t)$ pour l'arbre final sur une seule ligne.

Si $X = 1$, alors pour chaque cas de test, affichez $N$ lignes, la $i^{\text{ème}}$ ligne étant la valeur de $f(t)$ après la $i^{\text{ème}}$ requête.

Sous-tâches

• ($25$ points) $X = 0$.
• ($30$ points) Chaque $a_i$ est choisi uniformément au hasard dans $[1, i]$.
• ($45$ points) Aucune contrainte supplémentaire.

Exemples

Exemples 1

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

Sortie 1

3
5

Exemples 2

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

Sortie 2

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

Remarque

Explication de l'exemple 1

Pour le premier cas de test, nous pouvons colorier les sommets $1$, $2$, $4$ et $5$ en vert (notez qu'il y a $N + 1 = 5$ sommets puisqu'il y a déjà un sommet au début). Alors $\{1, 2\}$, $\{4\}$ et $\{5\}$ sont des composantes cool.

Pour le deuxième cas de test, nous pouvons colorier les sommets $1$, $4$, $5$, $6$, $8$ et $9$ en vert. Alors $\{1\}$, $\{4\}$, $\{5, 8\}$, $\{6\}$ et $\{9\}$ sont des composantes cool.

Explication de l'exemple 2

Cet exemple utilise les mêmes arbres que le premier, mais est de type $X = 1$.