310964: CF1914F. Programming Competition

F. Programming Competitiontime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

BerSoft is the biggest IT corporation in Berland. There are $n$ employees at BerSoft company, numbered from $1$ to $n$.

The first employee is the head of the company, and he does not have any superiors. Every other employee $i$ has exactly one direct superior $p_i$.

Employee $x$ is considered to be a superior (direct or indirect) of employee $y$ if one of the following conditions holds:

• employee $x$ is the direct superior of employee $y$;
• employee $x$ is a superior of the direct superior of employee $y$.

The structure of BerSoft is organized in such a way that the head of the company is superior of every employee.

A programming competition is going to be held soon. Two-person teams should be created for this purpose. However, if one employee in a team is the superior of another, they are uncomfortable together. So, teams of two people should be created so that no one is the superior of the other. Note that no employee can participate in more than one team.

Your task is to calculate the maximum possible number of teams according to the aforementioned rules.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of employees.

The second line contains $n-1$ integers $p_2, p_3, \dots, p_n$ ($1 \le p_i \le n$), where $p_i$ is the index of the direct superior of the $i$-th employee.

The sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

Output

For each test case, print a single integer — the maximum possible number of teams according to the aforementioned rules.

ExampleInput

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

Output

1
0
1
3
3
3

Note

In the first test case, team $(3, 4)$ can be created.

In the second test case, no team can be created, because there are only $2$ employees and one is the superior of another.

In the third test case, team $(2, 3)$ can be created.

In the fourth test case, teams $(2, 4)$, $(3, 5)$ and $(6, 7)$ can be created.

In the fifth test case, teams $(2, 3)$, $(6, 4)$ and $(5, 7)$ can be created.

题目大意：
BerSoft 是 Berland 最大的 IT 公司，公司有 n 名员工，编号从 1 到 n。第一个员工是公司负责人，他没有上级。每个其他员工 i 有一个直接上级 p_i。如果员工 x 是员工 y 的直接或间接上级，则认为他们之间有上下级关系。根据这个规则，需要创建两人团队参加编程比赛，但上下级关系的员工不能在同一队。要求计算根据上述规则可以创建的最大团队数。

输入数据格式：
第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。
每个测试用例的第一行包含一个整数 n（2 ≤ n ≤ 2 × 10^5），表示员工数量。
第二行包含 n-1 个整数 p_2, p_3, ..., p_n（1 ≤ p_i ≤ n），其中 p_i 是第 i 个员工的直接上级的索引。
所有测试用例的 n 之和不超过 2 × 10^5。

输出数据格式：
对于每个测试用例，输出一个整数，表示根据上述规则可以创建的最大团队数。

示例：
输入：
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
0
1
3
3
3

注意：
- 在第一个测试用例中，可以创建团队 (3, 4)。
- 在第二个测试用例中，无法创建团队，因为只有 2 名员工且一名是另一名的上级。
- 在第三个测试用例中，可以创建团队 (2, 3)。
- 在第四个测试用例中，可以创建团队 (2, 4)，(3, 5) 和 (6, 7)。
- 在第五个测试用例中，可以创建团队 (2, 3)，(6, 4) 和 (5, 7)。题目大意： BerSoft 是 Berland 最大的 IT 公司，公司有 n 名员工，编号从 1 到 n。第一个员工是公司负责人，他没有上级。每个其他员工 i 有一个直接上级 p_i。如果员工 x 是员工 y 的直接或间接上级，则认为他们之间有上下级关系。根据这个规则，需要创建两人团队参加编程比赛，但上下级关系的员工不能在同一队。要求计算根据上述规则可以创建的最大团队数。 输入数据格式： 第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。 每个测试用例的第一行包含一个整数 n（2 ≤ n ≤ 2 × 10^5），表示员工数量。 第二行包含 n-1 个整数 p_2, p_3, ..., p_n（1 ≤ p_i ≤ n），其中 p_i 是第 i 个员工的直接上级的索引。 所有测试用例的 n 之和不超过 2 × 10^5。 输出数据格式： 对于每个测试用例，输出一个整数，表示根据上述规则可以创建的最大团队数。 示例： 输入： 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 0 1 3 3 3 注意： - 在第一个测试用例中，可以创建团队 (3, 4)。 - 在第二个测试用例中，无法创建团队，因为只有 2 名员工且一名是另一名的上级。 - 在第三个测试用例中，可以创建团队 (2, 3)。 - 在第四个测试用例中，可以创建团队 (2, 4)，(3, 5) 和 (6, 7)。 - 在第五个测试用例中，可以创建团队 (2, 3)，(6, 4) 和 (5, 7)。