The Championship

Time limit1sMemory limit128 MB

Summary

Pair as many employees as possible so each team holds two people with neither managing the other.

Level: Hard8 of 10
Topics: Greedy, Tree, Heap, Sorting
Solved: No attempts yet

Problem

A company has a hierarchical chain of command.

Each employee has at most one direct manager.
The "is a manager of" relation is transitive: if A is a manager of B (not necessarily directly) and B is a manager of C, then A is a manager of C.
The relation has no cycles: there are no two distinct people A and B such that A is a manager of B while B is a manager of A at the same time.

The company decides to hold a beach volleyball championship contested by teams of two employees. So that nobody feels awkward, a team may be formed only from a pair (A, B) where A is not a manager of B and B is not a manager of A. Each employee can belong to at most one team.

What is the maximum number of teams that can enter the championship?

Input

The first line contains the number of test cases Z ( $1 \le Z \le 10$ ).

For each test case, the first line contains the number of employees N ( $1 \le N \le 100000$ ). The second line contains N integers $a_1, a_2, \dots, a_N$ , where $a_i$ is the index of the direct manager of employee $i$ ( $1 \le a_i \le N$ ). If employee $i$ has no manager, then $a_i = -1$ .

Output

For each test case, print on its own line the maximum number of teams that can enter the championship.

Examples7

Example 1
Input
```
2
6
-1 1 2 3 4 5
6
-1 -1 -1 1 4 5
```
Expected output
```
0
2
```
Example 2
Input
```
1
1
-1
```
Expected output
```
0
```
Example 3
Input
```
1
2
-1 -1
```
Expected output
```
1
```
Example 4
Input
```
1
2
-1 1
```
Expected output
```
0
```
Example 5
Input
```
1
5
-1 1 1 1 1
```
Expected output
```
2
```
Example 6
Input
```
1
3
-1 1 1
```
Expected output
```
1
```

Example 7

Input

3
4
-1 1 -1 3
1
-1
6
-1 -1 -1 -1 -1 -1

Expected output

2
0
3