Iris's Full Binary Tree

小 R 给出一棵以 $1$ 为根的树，第 $i\ (2 \leq i \leq n)$ 个点的父亲为 $p_i\ (1 \leq p_i \leq i - 1)$。 小 R 定义一棵树的二叉深度为，最小的 $d$ 满足，最大深度为 $d$ 的 **满二叉树**（它应拥有 $2^d - 1$ 个节点）拥有至少一个联通导出子图与该树同构。特别地，若所有 $d$ 均不满足条件，则其二叉深度为 $d = -1$。 对于所有 $k = 1\dots n$，小 R 想要求出树上仅保留编号为 $1 \sim k$ 的节点，组成的子图的二叉深度。

Iris likes full binary trees. Let's define the depth of a rooted tree as the maximum number of vertices on the simple paths from some vertex to the root. A full binary tree of depth $ d $ is a binary tree of depth $ d $ with exactly $ 2^d - 1 $ vertices. Iris calls a tree a $ d $ -binary tree if some vertices and edges can be added to it to make it a full binary tree of depth $ d $ . Note that any vertex can be chosen as the root of a full binary tree. Since performing operations on large trees is difficult, she defines the binary depth of a tree as the minimum $ d $ satisfying that the tree is $ d $ -binary. Specifically, if there is no integer $ d \ge 1 $ such that the tree is $ d $ -binary, the binary depth of the tree is $ -1 $ . Iris now has a tree consisting of only vertex $ 1 $ . She wants to add $ n - 1 $ more vertices to form a larger tree. She will add the vertices one by one. When she adds vertex $ i $ ( $ 2 \leq i \leq n $ ), she'll give you an integer $ p_i $ ( $ 1 \leq p_i < i $ ), and add a new edge connecting vertices $ i $ and $ p_i $ . Iris wants to ask you the binary depth of the tree formed by the first $ i $ vertices for each $ 1 \le i \le n $ . Can you tell her the answer?

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2 \leq n \leq 5 \cdot 10^5 $ ) — the final size of the tree. The second line of each test case contains $ n - 1 $ integers $ p_2, p_3, \ldots, p_n $ ( $ 1 \leq p_i < i $ ) — descriptions of all edges of the tree. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5 \cdot 10^5 $ .

For each test case output $ n $ integers, $ i $ -th of them representing the binary depth of the tree formed by the first $ i $ vertices.

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

In the first test case, the final tree is shown below: - The tree consisting of the vertex $ 1 $ has the binary depth $ 1 $ (the tree itself is a full binary tree of depth $ 1 $ ). - The tree consisting of the vertices $ 1 $ and $ 2 $ has the binary depth $ 2 $ (we can add the vertex $ 3 $ to make it a full binary tree of depth $ 2 $ ). - The tree consisting of the vertices $ 1 $ , $ 2 $ and $ 3 $ has the binary depth $ 2 $ (the tree itself is a full binary tree of depth $ 2 $ ). In the second test case, the formed full binary tree after adding some vertices to the tree consisting of $ n $ vertices is shown below (bolded vertices are added): The depth of the formed full binary tree is $ 4 $ . In the fifth test case, the final tree is shown below: It can be proved that Iris can't form any full binary tree by adding vertices and edges, so the binary depth is $ -1 $ .