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?

Format

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≤n≤10^5).

Then n−1 lines follow. The ith line contains a single number fi (0≤fi<i), which means that after the ith operation there is a new node numbered i and there is an edge between node i and node fi.

Output

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

Samples

4
0
0
1

1
2
2