Nikita plays a new computer game. There are $*m*$ levels in this game. In the beginning of each level a new class appears in the game; this class is a child-class of the class $*y*_{*i*}$ (and $*y*_{*i*}$ is called parent-class for this new class). Thus, the classes form a tree. Initially there is only one class with index $1$.

Changing the class to its neighbour (child-class or parent-class) in the tree costs $1$ coin. You can not change the class back. The cost of changing the class $*a*$ to the class $*b*$ is equal to the total cost of class changes on the path from $*a*$ to $*b*$ in the class tree.

Suppose that at $*i*$ -th level the maximum cost of changing one class to another is $*x*$. For each level output the number of classes such that for each of these classes there exists some other class $*y*$, and the distance from this class to $*y*$ is exactly $*x*$.

Input

First line contains one integer number $*m*$ — number of queries ($1 ≤ *m* ≤ 3·10^{5}$).

Next $*m*$ lines contain description of queries. $*i*$ -th line ($1 ≤ *i* ≤ *m*$) describes the $*i*$ -th level and contains an integer $*y*_{*i*}$ — the index of the parent-class of class with index $*i* + 1$ ($1 ≤ *y*_{*i*} ≤ *i*$).

Output

Suppose that at $*i*$ -th level the maximum cost of changing one class to another is $*x*$. For each level output the number of classes such that for each of these classes there exists some other class $*y*$, and the distance from this class to $*y*$ is exactly $*x*$.