Bob has a tree with ~N~ nodes, rooted at node ~1~. The nodes are numbered from ~1~ to ~N~. Each edge in the tree has a length of ~1~, and for every node ~i~ (~2 \le i \le N~), its parent is node ~p_i~, which satisfies ~1 \le p_i < i~.

For any two nodes ~u~ and ~v~, define the function:

$$\displaystyle g(u, v) = GCD\left(\text{dist}(u, \text{LCA}(u, v)), \text{dist}(v, \text{LCA}(u, v))\right) $$

Where:

• LCA(u, v) is the lowest common ancestor of nodes ~u~ and ~v~.
• dist(x, y) is the number of edges in the unique path between nodes ~x~ and ~y~.
• GCD(x, y) is the greatest common divisor of ~x~ and ~y~, with GCD(0, x) = x.

Bob wants to compute, for every integer ~x~ from ~1~ to ~N-1~, the number of unordered pairs ~(u, v)~ with ~1 \le u < v \le N~ such that ~g(u, v) = x~. Can you write a program to help Bob?

Input Specification

The first line of input contains one integer ~N~ (~2 \le N \le 2 \times 10^5~), the number of nodes.

Each of the following ~N-1~ lines contains one integer ~p_i~ (~1 \le p_i < i~), indicating the parent node of node ~i~.

Output Specification

Output ~N-1~ lines. The ~i~-th line contains one integer, the number of pairs ~(u, v)~ (~u < v~) so that ~g(u, v) = i~.

Constraints

For all test cases, ~2 \le N \le 2 \times 10^5~.

Subtask	Points	Additional constraints
~1~	~20~	~N \le 2000~
~2~	~15~	Each node has at most one child, except for the root node.
~3~	~15~	~N \le 5 \times 10^4~
~4~	~50~	No additional constraints.

Sample Input 1

5
1
2
2
1

Sample Output 1

8
2
0
0

Explanation for Sample 1

• There are ~8~ pairs of ~(u, v)~ with ~g(u, v)=1~: ~(1, 2)~, ~(1, 5)~, ~(2, 3)~, ~(2, 4)~, ~(2, 5)~, ~(3, 5)~, ~(4, 5)~, ~(3, 4)~.
• There are ~2~ pairs of ~(u, v)~ with ~g(u, v)=2~: ~(1, 3)~ and ~(1, 4)~.

Sample Input 2

8
1
2
3
4
1
6
6

Sample Output 2

16
9
2
1
0
0
0