BerSoft 是 Berland 最大的 IT 公司。 BerSoft 公司共有 $$$n$$$ 名员工,编号从 $$$1$$$ 到 $$$n$$$。
第一位员工是公司的负责人,他没有任何上级。每一位其他员工 $$$i$$$ 都有一位直接上级 $$$p_i$$$。
如果满足以下条件之一,员工 $$$x$$$ 被视为员工 $$$y$$$ 的上级(直接或间接):
- 员工$$$x$$$是员工$$$y$$$的直接上级;
- 员工$$$x$$$ 是员工$$$y$$$ 的直接上级的上级。
BerSoft 的组织结构是公司负责人高于每位员工。
编程比赛即将举行。为此目的应创建两人团队。然而,如果团队中的一名员工是另一名员工的上级,他们在一起就会感到不舒服。因此,应该创建两个人的团队,这样就没有一个人比另一个人更优越。请注意,任何员工都不能参与多个团队。
你的任务是根据上述规则计算最大可能的团队数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 员工数量。
第二行包含 $$$n-1$$$ 整数 $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i \le n$$$),其中 $$$p_i$$$ 是第 $$$i$$$ 员工的直接上级的索引。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 根据上述规则的最大可能团队数量。
示例
输入 #1
6 4 1 2 1 2 1 5 5 5 5 1 7 1 2 1 1 3 3 7 1 1 3 2 2 4 7 1 2 1 1 1 3
输出 #1
1 0 1 3 3 3
注意
在第一个测试用例中,可以创建团队$$$(3, 4)$$$。
在第二个测试用例中,无法创建任何团队,因为只有 $$$2$$$ 员工,并且其中一个是另一个的上级。
在第三个测试用例中,可以创建团队$$$(2, 3)$$$。
在第四个测试用例中,可以创建团队 $$$(2, 4)$$$、$$$(3, 5)$$$ 和 $$$(6, 7)$$$。
在第五个测试用例中,可以创建团队 $$$(2, 3)$$$、$$$(6, 4)$$$ 和 $$$(5, 7)$$$。