As a member of Coffee Chicken, ZYB is a boy with excellent data structure skills. 

Consider the following problem: Give a rooted tree with  vertices. Vertices are numbered from  to , and the root is always vertex . You are allowed to assign at most  key vertices so that the maximum ancient distances among all vertices is as small as possible. Denote the ancient distance of vertex  as: The distance between  and the first key vertex on the path from  to the root. For example, if the tree is 1-2-3 and the set of key vertices is , then the ancient distances of all vertices are .

ZYB then strengthens this problem: Please find the answer for each .  Could you accept ZYB's challenge?

输入描述:

The input contains multiple test cases. 
For each test case, the first line contains a integer , indicating the number of vertices in the tree.
In the second line, there are  integers, the -th integer  means that there is an edge between  and .
It's guaranteed that there are at most  test cases with , and the sum of  over all test cases will not exceed .

输出描述:

For each test case, you should output the sum of all answers instead of each of them.

3
1 2
3
1 1

3
2

The answer for the first test case is .
The answer for the second test case is .

备注:

If you have any possible solution, try it bravely!