410233: GYM103987 I Awson is God

Awson is our god, so sometimes we call him AoShen.

AoShen has $$$n$$$ fans, and each of them has a favourite number. They all know the favourite numbers of the others.

One day, AoShen asks his fans to play a game. Each person must tell AoShen the number of different favorite numbers among other fans'. Formally speaking, if the $$$j$$$-th fan's favorite number is $$$v_j$$$, then the $$$i$$$-th fan will tell AoShen the number of different elements in $$$\{v_j\mid 1\le j\le n,\, j\neq i\}$$$.

Take Walk_alone, Yzyyylx, Sinoey and Weierstras, who likes $$$5,5,14,114514$$$, respectively, as an example. The numbers they tell AoShen will be $$$3,3,2,2$$$.

However, some of them may cheat. For instance, if there are $$$3$$$ people and the numbers they tell AoShen are $$$1,2,100$$$, then obviously, AoShen is cheated. But AoShen may not be cheated if they tell him $$$1,2,2$$$, for it is possible that the first one likes $$$100$$$, and the rest of them like $$$200$$$.

AoShen hates cheaters, so he asks you to tell him the minimum number of people who are cheating.

The input contains several test cases.

The first line of the input contains an integer $$$T\ (1\le T\le 10)$$$, the number of test cases.

For each test case, the first line contains an integer $$$n\ (2\le n\le 10^5)$$$, the number of fans.

The second line contains $$$n$$$ integers. The $$$i$$$-th integer $$$a_i\ (1\le a_i\le 10^5)$$$ indicates the number that the $$$i$$$-th fan tells AoShen.

It is guaranteed that the sum of $$$n$$$ in all test cases does not exceed $$$10^5$$$.

Print a single number indicating the minimum number of cheaters.

The problem contains several subtasks. You can get the corresponding score for each passed test case.

• Subtask 1 ($$$50$$$ points): there is at most one cheater.
• Subtask 2 ($$$50$$$ points): no additional constraints.

3
3
1 2 100
4
3 3 3 3
5
1 2 3 4 5

1
0
3

In the first case, the third fans must be cheating.

In the second case, no one is cheating when all fans' favorite numbers are distinct.

In the third case, at least $$$3$$$ fans are cheating. When their favorite numbers are $$$1,3,1,2,2$$$, the numbers they tell AoShen should be $$$3,2,3,3,3$$$.