#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define mod 1000000007
#define sz(a) int32_t(a.size())
#define all(a) a.begin(), a.end()

// int prime[1000005];

// void sieve()
// {
//     prime[0]=prime[1]=0;
//     for(int i=2;i<1000005;i++)
//     {
//         prime[i]=1;
//     }

//     for(int i=2;i<1000005;i++)
//     {
//         if(prime[i]==1)
//         {
//             for(int j=i*i;j<1000005;j+=i)
//                 prime[j]=0;
//         }
//     }

//     for(int j=2;j<1000005;j++)
//         prime[j]=prime[j]+prime[j-1];
// }


void solve()
{
   
   int n;
   cin>>n;

   vector <int> v(n);

   for(int i=0;i<n;i++)
    cin>>v[i];

    map <int,int> mp;

    for(int i=0;i<n;i++)
    {
        mp[v[i]]++;
    }

    int ng = mp.size();

    map <int,int> um;

    for(auto x: mp)
    {
        um[x.second]++;
    }

    int mn=INT_MAX;
    int l=um.size(),c=0;
    //int cum=0;

    for(auto x:um)
    {
        int f=x.first,s=x.second;

        mn = min(mn, n - (f*s) - (ng-s)*f);

        ng-=s;

        //cout<<f<<" "<<s<<endl;

        //cout<<ng<<" ";

        // cum+= f*s;
        // c++;
    }

    cout<<mn<<endl;

    return;
    
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //sieve();
    int test=1;
    cin>>test;
    
    

    while(test--)
    {
        //dp.clear();
        //memset(dp,-1,sizeof(dp));
        solve();
    }
    
}
### 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>
using namespace std;
 
#define int long long
#define mod 1000000007
#define sz(a) int32_t(a.size())
#define all(a) a.begin(), a.end()

// int prime[1000005];

// void sieve()
// {
//     prime[0]=prime[1]=0;
//     for(int i=2;i<1000005;i++)
//     {
//         prime[i]=1;
//     }

//     for(int i=2;i<1000005;i++)
//     {
//         if(prime[i]==1)
//         {
//             for(int j=i*i;j<1000005;j+=i)
//                 prime[j]=0;
//         }
//     }

//     for(int j=2;j<1000005;j++)
//         prime[j]=prime[j]+prime[j-1];
// }


void solve()
{
   
   int n;
   cin>>n;

   vector <int> v(n);

   for(int i=0;i<n;i++)
    cin>>v[i];

    map <int,int> mp;

    for(int i=0;i<n;i++)
    {
        mp[v[i]]++;
    }

    int ng = mp.size();

    map <int,int> um;

    for(auto x: mp)
    {
        um[x.second]++;
    }

    int mn=INT_MAX;
    int l=um.size(),c=0;
    //int cum=0;

    for(auto x:um)
    {
        int f=x.first,s=x.second;

        mn = min(mn, n - (f*s) - (ng-s)*f);

        ng-=s;

        //cout<<f<<" "<<s<<endl;

        //cout<<ng<<" ";

        // cum+= f*s;
        // c++;
    }

    cout<<mn<<endl;

    return;
    
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //sieve();
    int test=1;
    cin>>test;
    
    

    while(test--)
    {
        //dp.clear();
        //memset(dp,-1,sizeof(dp));
        solve();
    }
    
}
```