Migrated from Lutece 455 Easy Tree Problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

A tree structure is very special structure, there is exactly one path connecting each pair of nodes.

Now, given a tree structure, which has $N$ nodes(conveniently labeled from $1$ to $N$). And the root of the tree is always labeled with $1$. You are to write a program to figure out that, for every node $V$ in the tree, how many nodes there are in the sub-tree rooted by $V$ and it’s label number is larger than the label number of $V$.

For the example above:

• $Ans_1 = 6, Ans_2 = 1, Ans_3 = 2, Ans_4 = 0, Ans_5 = 0, Ans_6 = 0, Ans_7 = 0$

Input

There are multiple cases.The first line is an integer $T$ representing the number of test cases.The following lines every tow lines representing a test case. For each case there are exactly two lines:The first line with a single integer $N$($1 \leq N \leq 200000$), representing the size of tree.The second line with $N – 1$ numbers: $P_2, P_3, \cdots P_n$. ($1 \leq P_i \leq N$),Which mean the father node of node $i$ is $P_i$.It is guaranteed that the input data is a tree structure and has $1$ as root.

Output

For each test case, output a line of $N$ numbers in the following format:

• Case #C: Ans[1] Ans[2] Ans[3] ... Ans[N]

Samples

2
7
1 1 3 2 1 3
4
1 2 3

Case #1: 6 1 2 0 0 0 0
Case #2: 3 2 1 0

Resources

The 5th ACM Programming Contest of HUST