E. Iris 的满二叉树

时间限制：4 秒
内存限制：1024 MB

Iris 喜欢满二叉树。

定义一棵有根树的深度为从某个顶点到根节点的简单路径上最多的顶点数。深度为 $d$ 的满二叉树是一棵深度为 $d$ 且恰好有 $2^d - 1$ 个顶点的二叉树。

Iris 称一棵树是 $d$-二叉树，如果可以通过向其中添加一些顶点和边，使其变成一棵深度为 $d$ 的满二叉树。注意，满二叉树的根可以是任意顶点。

由于在大型树上操作很困难，她定义一棵树的二叉树深度为满足该树是 $d$-二叉树的最小整数 $d$。特别地，如果不存在这样的 $d \ge 1$，则该树的二叉树深度为 $-1$。

Iris 现在有一棵只包含顶点 $1$ 的树。她想添加 $n-1$ 个顶点来形成一棵更大的树。她将逐个添加顶点。当她添加顶点 $i$（$2 \le i \le n$）时，她会给你一个整数 $p_i$（$1 \le p_i < i$），并添加一条连接顶点 $i$ 和 $p_i$ 的新边。

Iris 想让你回答：对于每个 $1 \le i \le n$，由前 $i$ 个顶点构成的树的二叉树深度是多少？

---

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 5 \cdot 10^5$）—— 树的最终大小。

每个测试用例的第二行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$（$1 \le p_i < i$）—— 所有边的描述。

数据保证：所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。

---

输出格式

对于每个测试用例，输出 $n$ 个整数，第 $i$ 个整数表示由前 $i$ 个顶点构成的树的二叉树深度。

---

示例

输入

7
3
1 1
6
1 2 3 4 5
7
1 1 3 2 5 1
10
1 1 2 1 4 2 4 5 8
10
1 1 3 1 3 2 2 2 6
20
1 1 2 2 4 4 5 5 7 6 8 6 11 14 11 8 13 13 12
25
1 1 3 3 1 5 4 4 6 8 11 12 8 7 11 13 7 13 15 6 19 14 10 23

输出

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

---

样例解释

第一个测试用例：最终树如下所示：

• 只包含顶点 $1$ 的树的二叉树深度为 $1$（它本身就是一棵深度为 $1$ 的满二叉树）。
• 包含顶点 $1$ 和 $2$ 的树的二叉树深度为 $2$（可以添加顶点 $3$ 使其成为深度为 $2$ 的满二叉树）。
• 包含顶点 $1$、$2$ 和 $3$ 的树的二叉树深度为 $2$（它本身就是一棵深度为 $2$ 的满二叉树）。

第二个测试用例：向 $n$ 个顶点的树添加一些顶点后形成的满二叉树如下所示（加粗的顶点是添加的）：

形成的满二叉树的深度为 $4$。

第五个测试用例：最终树如下所示：

可以证明 Iris 无法通过添加顶点和边形成任何满二叉树，因此二叉树深度为 $-1$。