在最近的一场 Codeforces 比赛后，Vasya 迷上了自己出题。Vasya 的想象力很匮乏，但他讨厌仙人掌（cactuses），所以他决定出一道关于树的题目。他很容易就想到了一个只需要在树上跑两次 DFS 的简单任务，但他遇到的下一个问题是如何为它生成测试数据。

Vasya 最喜欢的 testlib.h 中的函数是 wnext。为了方便起见，在本题中我们简化了它的定义，它的工作方式如下：

int wnext(int a, int b, int type) {
    int result = next(a, b);
    for (int i = 0; i < type; i++)
        result = max(result, next(a, b));
    for (int i = 0; i < -type; i++)
        result = min(result, next(a, b));
    return result;
}

函数 next(a, b) 返回区间 $[a; b]$ 内均匀分布的随机整数。

Vasya 想出了以下生成测试数据的方法：他生成一棵拥有 $n = 10000$ 个节点的树。树的节点编号为 $0$ 到 $n - 1$。他在 $[-4; 4]$ 区间内随机选择一个整数 type，然后遍历树的节点，从节点 $1$ 到节点 $n - 1$，在节点 $i$ 和节点 wnext(0, i - 1, type) 之间添加一条边。之后，Vasya 随机打乱树的节点。这个过程可以用以下代码描述：

int n = 10000;
int p[n];
for (int i = 0; i < n; ++i) {
    p[i] = i;
}
shuffle(p, p + n);
int type = next(-max_param, max_param);
for (int i = 1; i < n; ++i) {
    add_edge(p[i], p[wnext(0, i - 1, type)]);
}

这里 p 是 $0$ 到 $n - 1$ 整数的一个随机排列。

Vasya 用这种方法为他的题目生成了 100 个测试点。不巧的是，他忘记记录每个测试点所使用的参数 type 的值。给定 Vasya 生成的这些测试点，请帮助他恢复至少 90% 的测试点的参数值。所有测试点的参数都是独立选择的。

输入格式

第一行包含一个整数 $T$ —— 测试点的数量，该值始终等于 100。

接下来的 $T$ 行包含测试点的描述。每行以整数 $n$ 开始 —— 树中的节点数，该值始终等于 10000。接下来的 $n - 1$ 个整数 $p_1, p_2, \dots, p_{n-1}$ ($0 \le p_i \le n - 1, p_i \neq i$) 表示树的边 $(i, p_i)$。请注意，节点已被 Vasya 打乱，因此不保证 $p_i < i$。保证边 $(i, p_i)$ 构成一棵包含 $n$ 个节点的树。

在样例中，为了展示格式，设 $T = 2, n = 3$。样例并不是按照上述方法生成的，你的程序不会在样例上进行测试。第一个测试点与样例不同。

输出格式

输出 $T$ 个整数，每行一个，表示用于生成测试点的参数 type 的值。要通过该测试，你必须对至少 90 个测试点给出正确的预测。

样例

输入 1

2
3 0 1
3 0 0

输出 1

-2
1