我们都知道，丽卡数学不好。Yuta很担心这种情况。他给丽卡布置了很多数学作业，但她一个也没解决。所以，今天他提出了一个简单的问题来帮助她建立信心：

这是一个有m个节点的树，你可以删除树上的一些节点，并且不能有任何边连接两个剩余的节点。你需要最大化剩下的点数。

Rikka觉得这个任务太简单了，于是她想出了一个新问题：

一开始只有一个节点的树。然后每次她都将一个新节点链接到树上。每次操作后，您需要告诉她剩余的最大点数（如上所述）。

这个问题对丽卡来说太难了。你能帮助她吗？

测试用例不超过100个，测试用例不超过3个，测试用例为n>10^3。

对于每个测试用例，第一行包含一个数字n（1≤n≤10^5）。

然后是n−1行。第i行包含单个数字fi(0≤fi<i)，表示第i次操作后增加了一个编号为i的新节点，节点i与节点fi之间有一条边。

对于每个操作，您需要打印单行，其中包含一个数字-此操作后的答案。

4
0
0
1

1
2
2