Hello coders, today we are going to solve Madoka and Ladder Decomposition CodeChef Solution whose Problem Code is LADCOMP.

Madoka was given a tree on her coming of age, and not a simple one, but a rooted tree of n vertices with a root at the vertex with the number 1.

For all i â‰¥ 2, let Pi ( 1 â‰¤ Pi â‰¤ iâˆ’1) be the parent of the vertex i.

Let’s define the depth array h as follows: h1 = 1, and hi=hPi+1 for all i â‰¥ 2.

The subtree of a vertex u, denoted S(u), is defined as the set of vertices v such that the unique path from 1 to v contains u. Also, we define
valu=max{h(v):vâˆˆS(u)}.
A tree is divided into paths by a ladder decomposition if each vertex is located on exactly one path, and each vertex u with at least one child lies in the same path as its child v with the maximum valv, and if there are several such vertices, then the vertex with the minimum number is selected.

Madoka defines the beauty of a tree in the following way. Let the ladder decomposition of the path lengths be L1, . . . ,Lk, then the beauty of the tree is L21+L22+â‹¯+L2k
For each i (1â‰¤iâ‰¤n), your task is to calculate the beauty of the tree formed by the first i vertices.

## Input

• The first line contains an integer T – the number of test cases. Then T test cases follow.
• The first line of each test case contains a single integer n – the size of the tree.
• The second line contains n âˆ’ 1 integers P2, . . . ,Pn.

## Output

For each test case, print in a separate line a single integer – the answer to the problem.

## Constraints

• 1 â‰¤ T â‰¤ 10
• 2 â‰¤ n â‰¤8â‹…105
• 1 â‰¤ Pi <i for all 2 â‰¤ i â‰¤ n
• The sum of n over all test cases is at most 8â‹…105

• The sum of n is at most 2â‹…103.
• The time limit is 1 second.
• hi â‰¤ 3 for all i.
• The sum of n is at most 105.
• The time limit is 1 second.
• The sum of n is at most 2â‹…105.
• The time limit is 1 second.
• Original constraints.
• The time limit is 2.2 seconds.

Sample Input

``````2
6
1 2 1 4 3
12
1 2 1 4 4 6 2 8 5 6 11``````

Sample Output

``````0 1 4 4 5 10
0 1 4 4 5 5 10 10 13 14 14 21``````