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·105).
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_.
[samples]
Nikita 正在玩一款新电脑游戏。游戏中共有 $m$ 个关卡。在每个关卡开始时，游戏中会出现一个新的职业；这个新职业是职业 $y_i$ 的子职业（而 $y_i$ 被称为该新职业的父职业）。因此，这些职业构成了一棵树。初始时只有一个编号为 $1$ 的职业。
在树中将职业切换到其邻居（子职业或父职业）需要花费 $1$ 枚金币。你不能切换回之前的职业。将职业 $a$ 切换到职业 $b$ 的代价等于在职业树中从 $a$ 到 $b$ 的路径上所有切换操作的总代价。
假设在第 $i$ 个关卡时，任意两个职业之间切换的最大代价为 $x$。对于每个关卡，请输出满足以下条件的职业数量：对于每个这样的职业，都存在另一个职业 $y$，使得该职业到 $y$ 的距离恰好为 $x$。
## Input
第一行包含一个整数 $m$ —— 查询的数量（$1 ≤ m ≤ 3·10^5$）。接下来 $m$ 行描述每个查询。第 $i$ 行（$1 ≤ i ≤ m$）描述第 $i$ 个关卡，包含一个整数 $y_i$ —— 编号为 $i+1$ 的职业的父职业的编号（$1 ≤ y_i ≤ i$）。
## Output
假设在第 $i$ 个关卡时，任意两个职业之间切换的最大代价为 $x$。对于每个关卡，请输出满足以下条件的职业数量：对于每个这样的职业，都存在另一个职业 $y$，使得该职业到 $y$ 的距离恰好为 $x$。
[samples]
**Definitions**
Let $ m \in \mathbb{Z}^+ $ be the number of levels.
Let $ T = (V, E) $ be a tree evolving over levels, where:
- $ V = \{1, 2, \dots, m+1\} $ is the set of class indices.
- Initially, $ V = \{1\} $, and for each level $ i \in \{1, \dots, m\} $, a new node $ i+1 $ is added with parent $ y_i \in \{1, \dots, i\} $, so $ E = \{ (y_i, i+1) \mid i \in \{1, \dots, m\} \} $.
Let $ d(u, v) $ denote the shortest path distance (number of edges) between nodes $ u $ and $ v $ in $ T $.
Let $ D_i $ be the diameter of the tree at level $ i $ (i.e., the maximum distance between any two nodes in the tree after $ i $ levels have been added).
Let $ C_i $ be the number of nodes $ u $ in the tree at level $ i $ such that there exists a node $ v \ne u $ with $ d(u, v) = D_i $.
**Constraints**
1. $ 1 \le m \le 3 \cdot 10^5 $
2. For each $ i \in \{1, \dots, m\} $, $ 1 \le y_i \le i $
**Objective**
For each level $ i \in \{1, \dots, m\} $, output $ C_i $, the count of nodes that achieve the diameter $ D_i $ as an endpoint.