Question
Equal Elements
You are given an array A of size N. In one operation, you can do the following:
- Select indices i and j (𝑖 ≠ 𝑗) and set Ai = Aj.
Find the minimum number of operations required to make all elements of the array equal?
Input
The first line of input will contain a single integer T, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains an integer N - the size of the array.
The next line contains N space-separated integers, denoting the array A.
Constraints
1 ≤ T ≤ 1000
1 ≤ N ≤ 2x105
1 ≤ Ai ≤ N
The sum of N over all test cases won't exceed 2x105
Each test case consists of multiple lines of input.
The first line of each test case contains an integer N - the size of the array.
The next line contains N space-separated integers, denoting the array A.
Constraints
1 ≤ T ≤ 1000
1 ≤ N ≤ 2x105
1 ≤ Ai ≤ N
The sum of N over all test cases won't exceed 2x105
Output
For each test case, output on a new line, the minimum number of operations required to make all elements of the array equal.
Example
Sample Input
2
3
1 2 3
4
2 2 3 1
Sample Output
2
2
Explanation
Test case 1: The minimum number of operations required to make all elements of the array equal is 2.
Select indices 1 and 2 and set 𝐴1=𝐴2=2
Select indices 3 and 2 and set 𝐴3=𝐴2=2
Thus, the final array is [2, 2, 2].
Test case 2: The minimum number of operations required to make all elements of the array equal is 2.
Select indices 3 and 2 and set 𝐴3=𝐴2=2
Select indices 4 and 3 and set 𝐴4=𝐴3=2
Thus, the final array is [2, 2, 2].
2
3
1 2 3
4
2 2 3 1
Sample Output
2
2
Explanation
Test case 1: The minimum number of operations required to make all elements of the array equal is 2.
Select indices 1 and 2 and set 𝐴1=𝐴2=2
Select indices 3 and 2 and set 𝐴3=𝐴2=2
Thus, the final array is [2, 2, 2].
Test case 2: The minimum number of operations required to make all elements of the array equal is 2.
Select indices 3 and 2 and set 𝐴3=𝐴2=2
Select indices 4 and 3 and set 𝐴4=𝐴3=2
Thus, the final array is [2, 2, 2].