#include<bits/stdc++.h>
#define ll long long int
using namespace std;
bool sortbyfirstandsec(const pair<int,int> &a, 

              const pair<int,int> &b) 
{
if(a.first == b.first)

    return (a.second > b.second);

return a.first < b.first;
}
long long fact(long long int a, long long int b)
{
  if(b==0)
  return a;
  else
   return fact(b,a%b);
}

 
ll power(ll a, ll b) {
  ll ret=1;
    ll mod=1e9+7;
  while(b) {
    if(b%2) {
      ret=(ret*a)%mod;
    }
    a=(a*a)%mod;
    b/=2;
  }
  return ret;
}
 
ll foo(ll a, ll b) {
  ll mod=1e9+7;
  return (power(2,a+b)-power(2,b)+mod)%mod;
}
 /*
int main()
{*/
  signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  int t;
  cin>>t;
  while (t--)
  {
    
 
  long long int n, i,j,
   k, r=0,l,l1=0, s=0, r1=0, r2=0,m, z=0;
  cin>>n;
//  pair<long long int,long long int>p[n];
   long long int a[n], b[n], c, d=0,p, q;
 map<long long int,long long int>m1;
 for(i=0;i<n;i++)
 {
   cin>>a[i];
   m1[a[i]]++;
 }
 for(auto x:m1) 
 {
   b[r]=x.second;
   r++;
 }
 sort(b,b+r);
 q=2e6;
 for(i=0;i<r;i++)
 {
   p=n-b[i]*(r-i);
   q=min(q,p);
 }
 cout<<q<<endl;
 }
return 0;
}
### Prompt

Develop a solution in Cpp to the problem described below:

Polycarp was gifted an array a of length n. Polycarp considers an array beautiful if there exists a number C, such that each number in the array occurs either zero or C times. Polycarp wants to remove some elements from the array a to make it beautiful.

For example, if n=6 and a = [1, 3, 2, 1, 4, 2], then the following options are possible to make the array a array beautiful: 

  * Polycarp removes elements at positions 2 and 5, array a becomes equal to [1, 2, 1, 2]; 
  * Polycarp removes elements at positions 1 and 6, array a becomes equal to [3, 2, 1, 4]; 
  * Polycarp removes elements at positions 1, 2 and 6, array a becomes equal to [2, 1, 4]; 



Help Polycarp determine the minimum number of elements to remove from the array a to make it beautiful.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.

The first line of each test case consists of one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of the array a.

The second line of each test case contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9) — array a.

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

Output

For each test case, output one integer — the minimum number of elements that Polycarp has to remove from the array a to make it beautiful.

Example

Input


3
6
1 3 2 1 4 2
4
100 100 4 100
8
1 2 3 3 3 2 6 6


Output


2
1
2

### Response

```cpp
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
bool sortbyfirstandsec(const pair<int,int> &a, 

              const pair<int,int> &b) 
{
if(a.first == b.first)

    return (a.second > b.second);

return a.first < b.first;
}
long long fact(long long int a, long long int b)
{
  if(b==0)
  return a;
  else
   return fact(b,a%b);
}

 
ll power(ll a, ll b) {
  ll ret=1;
    ll mod=1e9+7;
  while(b) {
    if(b%2) {
      ret=(ret*a)%mod;
    }
    a=(a*a)%mod;
    b/=2;
  }
  return ret;
}
 
ll foo(ll a, ll b) {
  ll mod=1e9+7;
  return (power(2,a+b)-power(2,b)+mod)%mod;
}
 /*
int main()
{*/
  signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  int t;
  cin>>t;
  while (t--)
  {
    
 
  long long int n, i,j,
   k, r=0,l,l1=0, s=0, r1=0, r2=0,m, z=0;
  cin>>n;
//  pair<long long int,long long int>p[n];
   long long int a[n], b[n], c, d=0,p, q;
 map<long long int,long long int>m1;
 for(i=0;i<n;i++)
 {
   cin>>a[i];
   m1[a[i]]++;
 }
 for(auto x:m1) 
 {
   b[r]=x.second;
   r++;
 }
 sort(b,b+r);
 q=2e6;
 for(i=0;i<r;i++)
 {
   p=n-b[i]*(r-i);
   q=min(q,p);
 }
 cout<<q<<endl;
 }
return 0;
}
```