给定一棵包含 $n$ 个节点的树，你可以使用若干条任意长度的线段来覆盖树的所有边，并满足以下要求：

1. 每条边必须被覆盖且仅被覆盖一次；
2. 每条线段必须从一个叶子节点开始，并终止于其祖先节点。

你可以选择任意数量的线段，使得这些线段能够按照上述要求覆盖整棵树，但你需要最小化这些线段的最大长度。你的任务是求出这个最小值。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$)，表示树中节点的总数。

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

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行一个整数，表示线段最大长度的最小值。

样例

输入 1

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

输出 1

3
7

说明

对于第一个样例测试用例，示意图如下。红色、绿色和蓝色线段分别代表长度为 2、3 和 2 的三条线段。