#include<iostream>
#include <iomanip>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(int i=a;i<b;i++)
#define it(x,b)  for(auto &x:b)
#define NUM  1000000007
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
long long binpow(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2)%NUM;
    if (b % 2)
        return (((res * res)%NUM)* a)%NUM;
    else
        return (res * res)%NUM;
}
struct prep
{
    vll fact;
    vll inv;
    ll m;
    explicit prep(int n)
    {
        ll mod=NUM;
        int num=n;
        m=mod;
        fact.resize(n+31);
        inv.resize(n+31);
        fact[0]=1;
        inv[0]=1;
        for(int i=1;i<=num+30;i++)
        {
            fact[i]=(fact[i-1]*i)%mod;
            inv[i]=binpow(fact[i],mod-2)%NUM;
        }
    }
    ll ncr(ll n , ll r)
    {
        if(r>n||r<0)
        {
            return 0;
        }
        ll p = ((fact[n]*inv[r])%m);
        p=(p*(inv[n-r])%m);
        return p;
    }
    ll fac(ll num)
    {
        return fact[num];
    }
};
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};//unordered_map<pair<long long, long long>, bool, hash_pair> um;
bool isPrime(long long n) {
    if (n == 1)return false;
    if (n == 2)return true;
    for (long long i = 2; i * i <= n; i++)
        if (n % i == 0)return false;
    return true;
}
ll min(ll a,ll b)
{
    if(a>b)
    {
        return b;
    }
    return a;
}
ll max(ll a, ll b)
{
    if(a>b)
        return a;
    return b;
}
long long dif(long long a,long long b)
{
    if(a>b)
        return a-b;
    return b-a;
}
long long gcd(long long a,long long b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
long long lcm(long long a,long long b)
{
    long long k=gcd(a,b);
    return (a*b)/k;
}
void read(ll arr[],long long n)
{
    for(long long i=0;i<n;i++)
    {
        cin>>arr[i];
    }
}
void addedge(vector<vector<long long>>&v,long long p1,long long p2) {
    v[p1].push_back({p2});
    v[p2].push_back({p1});
}
bool mycmp(pair<long long ,float>p1,pair<long long ,float>p2)
{
    return p1.first<p2.first;
}
void print(ll arr[],ll n)
{
    for (long long i = 0; i < n; ++i) {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}
vector<long long >prime;
void sieveOferatosthenes(long long  MAX)
{
    bool pri[MAX + 1];
    memset(pri, true, sizeof(pri));
    pri[1] = false;

    for (long long  p = 2; p * p <= MAX; p++) {

        // If prime[p] is not changed, then it is a prime
        if (pri[p]) {

            // Set all multiples of p to non-prime
            for (long long  i = p * 2; i <= MAX; i += p)
                pri[i] = false;
        }
    }
    for(long long  i=1;i<=MAX;i++)
    {
        if(pri[i])
        {
            prime.push_back(i);
        }
    }
}
void solve()
{
    int n;cin>>n;
    ll arr[n];read(arr,n);
    map<ll,ll>m;
    vll v;
    ll sum2=0;
    for(int i=0;i<n;i++)
    {
        m[arr[i]]++;
    }
    for(auto it:m)
    {
        v.push_back(it.second);
        sum2+=v.back();
    }
    sort(v.begin(),v.end());
    ll sum=0;
    ll res=INT_MAX;
    for(int i=0;i<v.size();i++)
    {
        ll del=(sum2-(v.size()-i)*v[i])+sum;
        res=min(res,del);
        sum+=v[i];
        sum2-=v[i];
    }
    cout<<res<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;t=1;
    cin>>t;
    // WE WILL WIN.
    while(t--)
    {
        solve();
    }
}
### Prompt

In Cpp, your task is to solve the following problem:

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<iostream>
#include <iomanip>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(int i=a;i<b;i++)
#define it(x,b)  for(auto &x:b)
#define NUM  1000000007
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
long long binpow(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2)%NUM;
    if (b % 2)
        return (((res * res)%NUM)* a)%NUM;
    else
        return (res * res)%NUM;
}
struct prep
{
    vll fact;
    vll inv;
    ll m;
    explicit prep(int n)
    {
        ll mod=NUM;
        int num=n;
        m=mod;
        fact.resize(n+31);
        inv.resize(n+31);
        fact[0]=1;
        inv[0]=1;
        for(int i=1;i<=num+30;i++)
        {
            fact[i]=(fact[i-1]*i)%mod;
            inv[i]=binpow(fact[i],mod-2)%NUM;
        }
    }
    ll ncr(ll n , ll r)
    {
        if(r>n||r<0)
        {
            return 0;
        }
        ll p = ((fact[n]*inv[r])%m);
        p=(p*(inv[n-r])%m);
        return p;
    }
    ll fac(ll num)
    {
        return fact[num];
    }
};
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};//unordered_map<pair<long long, long long>, bool, hash_pair> um;
bool isPrime(long long n) {
    if (n == 1)return false;
    if (n == 2)return true;
    for (long long i = 2; i * i <= n; i++)
        if (n % i == 0)return false;
    return true;
}
ll min(ll a,ll b)
{
    if(a>b)
    {
        return b;
    }
    return a;
}
ll max(ll a, ll b)
{
    if(a>b)
        return a;
    return b;
}
long long dif(long long a,long long b)
{
    if(a>b)
        return a-b;
    return b-a;
}
long long gcd(long long a,long long b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
long long lcm(long long a,long long b)
{
    long long k=gcd(a,b);
    return (a*b)/k;
}
void read(ll arr[],long long n)
{
    for(long long i=0;i<n;i++)
    {
        cin>>arr[i];
    }
}
void addedge(vector<vector<long long>>&v,long long p1,long long p2) {
    v[p1].push_back({p2});
    v[p2].push_back({p1});
}
bool mycmp(pair<long long ,float>p1,pair<long long ,float>p2)
{
    return p1.first<p2.first;
}
void print(ll arr[],ll n)
{
    for (long long i = 0; i < n; ++i) {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}
vector<long long >prime;
void sieveOferatosthenes(long long  MAX)
{
    bool pri[MAX + 1];
    memset(pri, true, sizeof(pri));
    pri[1] = false;

    for (long long  p = 2; p * p <= MAX; p++) {

        // If prime[p] is not changed, then it is a prime
        if (pri[p]) {

            // Set all multiples of p to non-prime
            for (long long  i = p * 2; i <= MAX; i += p)
                pri[i] = false;
        }
    }
    for(long long  i=1;i<=MAX;i++)
    {
        if(pri[i])
        {
            prime.push_back(i);
        }
    }
}
void solve()
{
    int n;cin>>n;
    ll arr[n];read(arr,n);
    map<ll,ll>m;
    vll v;
    ll sum2=0;
    for(int i=0;i<n;i++)
    {
        m[arr[i]]++;
    }
    for(auto it:m)
    {
        v.push_back(it.second);
        sum2+=v.back();
    }
    sort(v.begin(),v.end());
    ll sum=0;
    ll res=INT_MAX;
    for(int i=0;i<v.size();i++)
    {
        ll del=(sum2-(v.size()-i)*v[i])+sum;
        res=min(res,del);
        sum+=v[i];
        sum2-=v[i];
    }
    cout<<res<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;t=1;
    cin>>t;
    // WE WILL WIN.
    while(t--)
    {
        solve();
    }
}
```