Simple Problem

Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation. He's given Rikka many math tasks to practice but she hasn't solved any of them. So, today he comes up with a simple problem to help her build up confidence: Here is a tree with $m$ nodes, you can delete some of the nodes on the tree and there mustn't be any edges connecting two remained nodes. You need to maximize the number of the points remained. Rikka thinks this task is too simple, so she comes up with a new problem: At first there is a tree with only one node. And then each time she links a new node to the tree. After each operation, you need to tell her the maximum number of the points remained (as described above). This problem is too difficult for Rikka to solve. Can you help her?

Input

There are no more than 100 testcases and there are no more than 3 testcases with $n > 10^3$. For each testcase, the first line contains a number $n\ (1 \leq n \leq 10^5)$. Then $n-1$ lines follow. The $i$th line contains a single number $f_i \ (0 \leq f_i <i)$, which means that after the $i$th operation there is a new node numbered $i$ and there is an edge between node $i$ and node $f_i$.

Output

For each operation you need to print a single line with a single number - the answer after this operation.

Sample Input

4
0
0
1

Sample Output

1
2
2

Author

XJZX

Source

2015 Multi-University Training Contest 4