Pracowity bóbr dekoruje choinkę, ale ma dość dziwne preferencje co do używanych kolorów.

Rozważmy kolorowanie wierzchołków drzewa przy użyciu dwóch kolorów: czerwonego i zielonego.

W danym kolorowaniu spójną składową zielonych wierzchołków nazywamy fajną, jeśli co najwyżej dwa czerwone wierzchołki są z nią sąsiednie. Dla drzewa $t$, niech $f(t)$ oznacza maksymalną liczbę fajnych składowych w dowolnym kolorowaniu $t$.

Dane jest drzewo $t$, początkowo zawierające tylko jeden wierzchołek, oznaczony jako wierzchołek $1$. Wykonaj $N$ zapytań; w $i$-tym zapytaniu dodaj wierzchołek liściowy, dołączając go do wierzchołka $a_i$. Istnieją dwa typy przypadków testowych, zależne od zmiennej $X \in \{0, 1\}$:

• Jeśli $X = 0$, wypisz $f(t)$ po zakończeniu wszystkich zapytań.
• Jeśli $X = 1$, wypisz $f(t)$ po każdym zapytaniu.

Wejście

Dostępnych jest wiele przypadków testowych. Plik wejściowy rozpoczyna się od $T$ oraz $X$ ($1 \le T \le 4\cdot 10^4$, $X \in \{0, 1\}$), oznaczających odpowiednio liczbę przypadków testowych oraz typ testu.

Pierwsza linia każdego przypadku testowego zawiera liczbę całkowitą $N$ ($1 \le N \le 2 \cdot 10^5$).

Druga linia zawiera $N$ liczb całkowitych $a_1, \dots, a_N$ ($1 \le a_i \le i$).

Gwarantuje się, że suma $N$ we wszystkich przypadkach testowych nie przekracza $4 \cdot 10^5$.

Wyjście

Jeśli $X = 0$, to dla każdego przypadku testowego wypisz $f(t)$ dla końcowego drzewa w pojedynczej linii.

Jeśli $X = 1$, to dla każdego przypadku testowego wypisz $N$ linii, gdzie $i$-ta linia zawiera wartość $f(t)$ po $i$-tym zapytaniu.

Podzadania

• ($25$ punktów) $X = 0$.
• ($30$ punktów) Każde $a_i$ jest wybierane jednostajnie losowo z przedziału $[1, i]$.
• ($45$ punktów) Brak dodatkowych ograniczeń.

Przykład

Przykład 1

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

Wyjście 1

3
5

Przykład 2

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

Wyjście 2

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

Uwagi

Wyjaśnienie przykładu 1

Dla pierwszego przypadku testowego możemy pokolorować wierzchołki $1$, $2$, $4$ i $5$ na zielono (zauważ, że istnieje $N + 1 = 5$ wierzchołków, ponieważ na początku istnieje już jeden wierzchołek). Wtedy $\{1, 2\}$, $\{4\}$ oraz $\{5\}$ są fajnymi składowymi.

Dla drugiego przypadku testowego możemy pokolorować wierzchołki $1$, $4$, $5$, $6$, $8$ i $9$ na zielono. Wtedy $\{1\}$, $\{4\}$, $\{5, 8\}$, $\{6\}$ oraz $\{9\}$ są fajnymi składowymi.

Wyjaśnienie przykładu 2

Ten przykład zawiera te same drzewa co pierwszy, ale jest typu $X = 1$.