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$。