Going to the Cinema

Description:

Input:

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

Each test case consists of two lines. The first line contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of people in the company.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n - 1$$$) — integers from peoples' claims.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output:

For each test case, print a single integer — the number of different ways to choose a set of people going to the cinema so that nobody becomes sad.

Sample Input:

4
2
1 1
7
0 1 2 3 4 5 6
8
6 0 3 3 6 7 2 7
5
3 0 0 3 3

Sample Output:

2
1
3
2

Note:

In the first test case, both people want to go to the cinema if and only if the other person goes. There are two valid options: either both people go, or neither of them goes. However, if just one of them goes, both will be sad.

In the second test case, everyone has to go to the cinema. In any other case, someone will be sad.

In the third test case, there are three valid options: person number $$$2$$$ goes to the cinema; or persons with indices $$$2, 3, 4, 7$$$ go; or all eight people go.