With just a few hours left until Penchick and Chloe leave for Singapore, they could hardly wait to see the towering trees at the Singapore Botanic Gardens! Attempting to contain their excitement, Penchick crafted a rooted tree to keep Chloe and himself busy.

Penchick has a rooted tree$^{\text{∗}}$ consisting of $n$ vertices, numbered from $1$ to $n$, with vertex $1$ as the root, and Chloe can select a non-negative integer $d$ to create a perfect binary tree$^{\text{†}}$ of depth $d$.

Since Penchick and Chloe are good friends, Chloe wants her tree to be isomorphic$^{\text{‡}}$ to Penchick's tree. To meet this condition, Chloe can perform the following operation on her own tree any number of times:

• Select an edge $(u,v)$, where $u$ is the parent of $v$.
• Remove vertex $v$ and all the edges connected to $v$, then connect all of $v$'s previous children directly to $u$.

In particular, doing an operation on an edge $(u, v)$ where $v$ is a leaf will delete vertex $v$ without adding any new edges.

Since constructing a perfect binary tree can be time-consuming, Chloe wants to choose the minimum $d$ such that a perfect binary tree of depth $d$ can be made isomorphic to Penchick's tree using the above operation. Note that she can't change the roots of the trees.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^6$) — the number of vertices in Penchick's tree.

The second line of each test case contains $n-1$ integers $p_2, p_3, \ldots, p_n$ ($1 \leq p_i \leq i-1$) — the parent of vertex $i$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single integer on each line: the minimum depth of Chloe's perfect binary tree.

见题面 Input 部分

见题面 Output 部分

For the first test case, create a perfect binary tree with depth $2$.

Consider carrying out the operation on edge $AC$. Then the edges $AC$, $CF$, and $CG$ are removed, and edges $AF$ and $AG$ are added.

The resulting tree is isomorphic to the tree given in the input. It can be proven that no sequence of operations carried out on a binary tree of depth less than $2$ can lead to a tree isomorphic to the tree given in the input.

In the second test case, the tree is already isomorphic to a perfect binary tree of depth $3$.