Description

树镇一年一度的松拉马大赛将要举行了。正如它的名字，树镇由 $n$ 座建筑和 $n-1$ 条街道组成，从任何建筑出发，经过一些街道总可以到达任意其他建筑。

树镇的松拉马大赛不仅比拼选手从起点到终点的跑步耗时，也比拼选手的力气，因为选手需要拉着松树通过某些街道。主办方并没有确定选手应该在多少条街道上拉着松树跑，更没确定这些街道具体是哪些街道。但是如果确定了这些街道，主办方将选择树上包含这些街道的简单路径中最长的一条作为比赛路段。

为了为主办方提供决策依据，你需要计算对于当主办方确定了选择 $k$ 条街道时（但没有确定这 $k$ 条街道具体是哪些街道），比赛路段的最小可能长度。一条简单路径的长度被定义为这条路径上包含的街道条数。

Input

第一行一个整数 $T$ ($1\le T\le 100$)，表示测试点个数。

对于每个测试点，第一行一个整数 $n$ ($2\le n\le 10^5$)，表示树镇的建筑物数。

第二行 $n-1$ 个整数 $p_2,p_3,\ldots,p_n$ ($1\le p_i<i$)，$p_i$ 表示 $i$ 的父节点。

保证对于所有测试点，$\sum n\le 3\times 10^5$。

Output

对于每个测试点，输出一行 $n-1$ 个整数，表示 $k=i$ 时的答案。如果不存在包含 $i$ 条街道的简单路径，输出 $-1$。请勿输出行末空格。

Samples

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

1
3 2 3 -1
4 2 4 4 -1
3 3 3 4 -1

Resources

The 22nd UESTC Programming Contest Preliminary