Mamy $n$ Mahou Shoujo siedzących w kręgu, ponumerowanych zgodnie z ruchem wskazówek zegara od 1 do $n$. Wśród nich niektóre są tak naprawdę Majo.

W ciągu następnych $n-3$ dni, dzień po dniu, mają miejsce następujące wydarzenia:

• W nocy, dokładnie jedna Majo budzi się i zabija pierwszą żywą Mahou Shoujo po swojej lewej lub prawej stronie (ta osoba również może być Majo).
• Rankiem wszyscy się budzą i odkrywają martwą Mahou Shoujo.

Kamome, jako sędzia Mahou Shoujo, musi po każdym poranku, w którym odkryto martwą Mahou Shoujo, znaleźć minimalną liczbę Majo, które mogły być obecne pierwszego dnia.

Obrazek 1: Wyrok

Wejście

Każdy zestaw testowy zawiera wiele przypadków testowych. Pierwszy wiersz zawiera liczbę całkowitą $t$ ($1 \le t \le 10^5$), oznaczającą liczbę przypadków testowych. Opis przypadków testowych następuje poniżej.

Pierwszy wiersz zawiera dwie liczby całkowite $n$ ($4 \le n \le 2 \times 10^5$, $1 < \sum n \le 10^6$), oznaczające liczbę Mahou Shoujo.

Drugi wiersz zawiera $n-3$ liczb całkowitych $p_i$ ($1 \le p_i \le n$, $p_i \ne p_j$ dla $1 < i < j < n-3$), oznaczających Mahou Shoujo, która zmarła $i$-tego dnia.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający $n-3$ liczb całkowitych, oznaczających minimalną liczbę Majo, które mogły być obecne pierwszego dnia po odkryciu martwej Mahou Shoujo $i$-tego dnia.

Przykład

Wejście 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

Wyjście 1

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

Uwagi

Dla drugiego przypadku testowego, trzeciego dnia co najmniej 2 Majo mogły być obecne pierwszego dnia. Możliwy przykład: Majo to 3 i 4, przy czym 3 zabija 2 pierwszego dnia, 3 zabija 1 drugiego dnia, a 4 zabija 3 trzeciego dnia.

Obrazek 2: Przykładowa sytuacja