// Problem Link -
#include <bits/stdc++.h>
using namespace std;

#define ll                   long long int
#define endl                 '\n'
#define pb                   push_back
#define mod                  1000000007
#define M2                   998244353
#define inf                  1e18
#define ff                   first
#define ss                   second
#define w(x)                 ll x=1; cin>>x; while(x--)
#define mid_of(l,r)          (l+(r-l)/2)
#define pii                  pair<ll,ll>
#define vi                   vector<ll>
#define mii                  unordered_map<ll, ll>
#define sii                  unordered_set<ll>
#define ps(x,y)              fixed<<setprecision(y)<<x
#define loop(i,a,b)          for(ll i = (a); i <= (b); i++)
#define looprev(i,b,a)       for(ll i = (b); i >= (a); i--)
#define mem(dp, val)         memset(dp, val, sizeof(dp))
#define setbits(x)           __builtin_popcountll(x)
#define pq_max               priority_queue<ll>
#define pq_min               priority_queue<ll,vector<ll>,greater<ll>>
#define all(v)               v.begin(), v.end()
#define allrev(v)            v.rbegin(), v.rend()
#define logarr(arr,a,b)      for(ll i=(a);i<=(b);i++) cout<<(arr[i])<<" "; cout<<"\n";
#define fast_io              ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

ll n;
vi v;
map<ll, ll> mymap;
ll total = 0;

void solve() {
    cin >> n;
    v.resize(n);
    mymap.clear();

    loop(i, 0, n - 1) {
        cin >> v[i];
        mymap[v[i]]++;
    }

    vi temp;
    temp.push_back(0);
    total = 0;
    for(auto p : mymap) {
        temp.push_back(p.ss);
        total += p.ss;
    }

    sort(temp.begin(), temp.end());

    ll ans = inf, help;
    ll sz = temp.size();
    vi sums(sz + 5);

    loop(i, 1, sz - 1) {
        sums[i] = temp[i];
        sums[i] += sums[i - 1];
    }

    // loop(i, 1, sz - 1) {
    //     cout << temp[i] << " ";
    // }
    // cout << endl;

    // loop(i, 1, sz - 1) {
    //     cout << sums[i] << " ";
    // }
    // cout << endl;

    ll i = 1, j = 1;
    total = sums[sz - 1];

    ll hero;

    while(i < sz) {
        j = i;
        while(j < sz and temp[i] == temp[j]) {
            j++;
        }

        help = 0;
        if(i != 1)
            help += sums[i - 1];

        hero = (total - sums[j - 1] - ((sz - j ) * temp[i]));
        // help += (total - sums[j - 1]);
        help += hero;

        ans = min(ans, help);

        i = j;
    }

    cout << ans << endl;
}

int32_t main() {
    fast_io;

    ll ntc = 1;
    cin >> ntc;

    for(ll t = 1; t <= ntc; t++) {
        // cout << "Case #" << t << ": ";
        solve();
    }

    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
// Problem Link -
#include <bits/stdc++.h>
using namespace std;

#define ll                   long long int
#define endl                 '\n'
#define pb                   push_back
#define mod                  1000000007
#define M2                   998244353
#define inf                  1e18
#define ff                   first
#define ss                   second
#define w(x)                 ll x=1; cin>>x; while(x--)
#define mid_of(l,r)          (l+(r-l)/2)
#define pii                  pair<ll,ll>
#define vi                   vector<ll>
#define mii                  unordered_map<ll, ll>
#define sii                  unordered_set<ll>
#define ps(x,y)              fixed<<setprecision(y)<<x
#define loop(i,a,b)          for(ll i = (a); i <= (b); i++)
#define looprev(i,b,a)       for(ll i = (b); i >= (a); i--)
#define mem(dp, val)         memset(dp, val, sizeof(dp))
#define setbits(x)           __builtin_popcountll(x)
#define pq_max               priority_queue<ll>
#define pq_min               priority_queue<ll,vector<ll>,greater<ll>>
#define all(v)               v.begin(), v.end()
#define allrev(v)            v.rbegin(), v.rend()
#define logarr(arr,a,b)      for(ll i=(a);i<=(b);i++) cout<<(arr[i])<<" "; cout<<"\n";
#define fast_io              ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

ll n;
vi v;
map<ll, ll> mymap;
ll total = 0;

void solve() {
    cin >> n;
    v.resize(n);
    mymap.clear();

    loop(i, 0, n - 1) {
        cin >> v[i];
        mymap[v[i]]++;
    }

    vi temp;
    temp.push_back(0);
    total = 0;
    for(auto p : mymap) {
        temp.push_back(p.ss);
        total += p.ss;
    }

    sort(temp.begin(), temp.end());

    ll ans = inf, help;
    ll sz = temp.size();
    vi sums(sz + 5);

    loop(i, 1, sz - 1) {
        sums[i] = temp[i];
        sums[i] += sums[i - 1];
    }

    // loop(i, 1, sz - 1) {
    //     cout << temp[i] << " ";
    // }
    // cout << endl;

    // loop(i, 1, sz - 1) {
    //     cout << sums[i] << " ";
    // }
    // cout << endl;

    ll i = 1, j = 1;
    total = sums[sz - 1];

    ll hero;

    while(i < sz) {
        j = i;
        while(j < sz and temp[i] == temp[j]) {
            j++;
        }

        help = 0;
        if(i != 1)
            help += sums[i - 1];

        hero = (total - sums[j - 1] - ((sz - j ) * temp[i]));
        // help += (total - sums[j - 1]);
        help += hero;

        ans = min(ans, help);

        i = j;
    }

    cout << ans << endl;
}

int32_t main() {
    fast_io;

    ll ntc = 1;
    cin >> ntc;

    for(ll t = 1; t <= ntc; t++) {
        // cout << "Case #" << t << ": ";
        solve();
    }

    return 0;
}
```