G. Galactic Reassigment
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

The Galactic Empire has organized its planets in a strict chain of command. At the very top lies Coruscant, the capital of the system. The planets are numbered from $$$1$$$ to $$$n$$$ according to their closeness to Coruscant (being Coruscat the planet with number $$$1$$$). Every other planet $$$u$$$ has a direct supervisor $$$p_u$$$ with $$$1 \le p_u \lt u$$$, forming a rooted tree with root in planet Coruscant.

Emperor Palpatine has decreed that all planets must be directly supervised by Coruscant, eliminating intermediate overseers (i.e., in the end every $$$u \ge 2$$$ must satisfy $$$p_u=1$$$).

You are granted the following operation:

  • Choose a planet $$$u$$$. For every planet $$$v$$$ on the chain of command from $$$u$$$ up to Coruscant (including $$$u$$$ but excluding Coruscant), reassign its supervisor to be the planet immediately closer to Coruscant; that is, decrement $$$p_v$$$ by one (set $$$p_u \leftarrow p_v - 1$$$). This gradual decrement by one is required to avoid instability within the Empire, since sudden jumps in authority could trigger rebellion and chaos.

Your task is to determine the minimum number of operations required so that, after applying them, every planet reports directly to Coruscant.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — the number of test cases.

Each test case begins with a line containing an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of planets. The second line contains $$$n-1$$$ integers $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i \lt i$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer: the minimum number of operations needed so that $$$p_u = 1$$$ for all $$$u = 2,3,\dots,n$$$.

Example
Input
3
4
1 2 1
4
1 2 2
4
1 2 3
Output
1
2
2