Iris 喜欢满二叉树。

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

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

由于在大型树上进行操作很困难，她将树的二叉深度（binary depth）定义为满足该树是 $d$-二叉树的最小 $d$。具体来说，如果不存在整数 $d \ge 1$ 使得该树是 $d$-二叉树，则该树的二叉深度为 $-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$ 个顶点组成的树的二叉深度。

样例

输入样例 1

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

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