Busy Beaver 正在裝飾一棵聖誕樹，但他對於使用什麼顏色有一些奇怪的偏好。

考慮對一棵樹的頂點進行著色，使用兩種顏色：紅色和綠色。

在著色中，如果一個綠色頂點組成的連通分量與至多兩個紅色頂點相鄰，則稱該連通分量為「酷」（cool）。對於一棵樹 $t$，令 $f(t)$ 為在 $t$ 的所有著色方案中，「酷」連通分量的最大數量。

有一棵樹 $t$，初始時僅包含一個頂點，標記為頂點 $1$。執行 $N$ 次查詢；在第 $i$ 次查詢中，透過將一個葉節點連接到頂點 $a_i$ 來新增一個頂點。根據變數 $X \in \{0, 1\}$，測試案例分為兩種類型：

• 若 $X = 0$，輸出所有查詢完成後 $f(t)$ 的值。
• 若 $X = 1$，輸出每次查詢後 $f(t)$ 的值。

輸入格式

輸入包含多個測試案例。輸入檔案開頭為 $T$ 和 $X$ ($1 \le T \le 4\cdot 10^4$, $X \in \{0, 1\}$)，分別代表測試案例的數量和測試類型。

每個測試案例的第一行包含一個整數 $N$ ($1 \le N \le 2 \cdot 10^5$)。

第二行包含 $N$ 個整數 $a_1, \dots, a_N$ ($1 \le a_i \le i$)。

保證所有測試案例的 $N$ 之總和不超過 $4 \cdot 10^5$。

輸出格式

若 $X = 0$，則對於每個測試案例，在單行輸出最終樹的 $f(t)$。

若 $X = 1$，則對於每個測試案例，輸出 $N$ 行，第 $i$ 行為第 $i$ 次查詢後 $f(t)$ 的值。

子任務

• ($25$ 分) $X = 0$。
• ($30$ 分) 每個 $a_i$ 均從 $[1, i]$ 中均勻隨機選擇。
• ($45$ 分) 無額外限制。

範例

範例輸入 1

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

範例輸出 1

3
5

範例輸入 2

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

範例輸出 2

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

說明

範例說明 1

對於第一個測試案例，我們可以將頂點 $1$、$2$、$4$ 和 $5$ 塗成綠色（注意，由於初始時已有一個頂點，總共有 $N + 1 = 5$ 個頂點）。此時 $\{1, 2\}$、$\{4\}$ 和 $\{5\}$ 為「酷」連通分量。

對於第二個測試案例，我們可以將頂點 $1$、$4$、$5$、$6$、$8$ 和 $9$ 塗成綠色。此時 $\{1\}$、$\{4\}$、$\{5, 8\}$、$\{6\}$ 和 $\{9\}$ 為「酷」連通分量。

範例說明 2

此範例與第一個範例使用相同的樹，但類型為 $X = 1$。