Il y a $n$ Mahou Shoujo assises en cercle, numérotées dans le sens des aiguilles d'une montre de 1 à $n$. Parmi elles, certaines sont en réalité des Majo. Pendant les $n-3$ jours suivants, les événements suivants se produisent un par un : La nuit, exactement une Majo se réveille et tue la première Mahou Shoujo vivante à sa gauche ou à sa droite (cette personne peut aussi être une Majo) ; Le matin, tout le monde se réveille et découvre la Mahou Shoujo morte.
Kamome, en tant que juge des Mahou Shoujo, doit déterminer, après chaque matin où une Mahou Shoujo morte est découverte, le nombre minimum de Majo qui auraient pu être présentes le premier jour.
Picture 1: The Judgement
Entrée
Chaque cas de test contient plusieurs cas de test. La première ligne contient un entier $t$ ($1 \le t \le 10^5$), indiquant le nombre de cas de test. La description des cas de test suit.
La première ligne contient deux entiers $n$ ($4 \le n \le 2 \times 10^5$, $1 < \sum n \le 10^6$), indiquant le nombre de Mahou Shoujo.
La deuxième ligne contient $n-3$ entiers $p_i$ ($1 \le p_i \le n$, $p_i \ne p_j$ pour $i \ne j$), indiquant la Mahou Shoujo qui est morte le $i$-ème jour.
Sortie
Pour chaque cas de test, affichez une ligne contenant $n-3$ entiers, indiquant le nombre minimum de Majo qui auraient pu être présentes le premier jour après la découverte de la Mahou Shoujo morte le $i$-ème jour.
Exemples
| standard input | standard output |
|---|---|
| 5 | 1 1 1 1 1 |
| 5 | |
| 1 2 | 1 1 2 2 3 3 3 |
| 6 | |
| 2 1 3 | 1 2 2 3 3 3 3 |
| 9 | |
| 1 2 3 4 5 6 | |
| 10 | |
| 1 3 5 7 9 2 4 | |
| 10 | |
| 2 5 1 8 10 9 4 |
Remarque
Pour le deuxième cas de test, le troisième jour, au moins 2 Majo auraient pu être présentes le premier jour. Un exemple possible est que 3 et 4 soient les Majo, où 3 tue 2 le premier jour, 3 tue 1 le deuxième jour, et 4 tue 3 le troisième jour.
Picture 2: A possible example