 #include <bits/stdc++.h>
    #include <string.h>
    using namespace std;
    
    #define ar array
    #define ll long long
    #define pb push_back
    #define fr(i,n) for(long long i=0;i<n;i++)
    
    const int MAX_N = 1e5 + 1;
    const int MOD = 1e9 + 7;
    const int INF = 1e9;
    const ll LINF = 1e18;
    ll power(ll x, ll y, ll M) {ll res = 1; while (y > 0) {if (y & 1) res = (res * x) % M; y >>= 1; x = (x * x) % M;} return res % M;}
    ll power(ll x, ll y) {ll res = 1; while (y > 0) {if (y & 1) res = (res * x); y >>= 1; x = (x * x);} return res;}
    
    bool sortcol( const vector<ll>& v1, const vector<ll>& v2 ) { 
 return v1[0] < v2[0]; 
} 

void sortArr(vector<pair<ll, ll> > & vp,ll v[], int n) 
            { 
    for (int i = 0; i < n; ++i) { 
        vp.push_back(make_pair(v[i], i)); 
    } 
  
    sort(vp.begin(), vp.end()); 
} 

int max(int a, int b) { return (a > b)? a : b; } 
int max(int a, int b, int c) { return max(max(a, b), c); }  
bool isPalindrome(string str)
{
    int j = str.length() - 1;

    for (int i = 0; i < j; i++, j--)
    {
        if (str[i] != str[j])
        {
            return false;
        }
    }

    return true;
}
void printDivisors(int n, std::vector<long> &v) 
{ 
    
    for (int i=1; i<=sqrt(n); i++) 
    { 
        if (n%i == 0) 
        { 
            
            if (n/i == i) 
                v.pb(i);  
            else 
            {
                v.pb(i);
                v.pb(n/i);
            }
        } 
    } 
} 
bool isPrime(int n) 
{ 
     
    if (n <= 1) 
        return false; 
    if (n <= 3) 
        return true; 
    if (n % 2 == 0 || n % 3 == 0) 
        return false; 
  
    for (int i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return false; 
  
    return true; 
} 


void solve() 
    {
        ll n;
        cin>>n;
        ll a[n];
        ll b[n+1];
        b[n]=0;
        fr(i,n)
        {
            cin>>a[i];
            b[i]=0;
        }
        sort(a,a+n);
        ll st=a[0];
        ll count=0;
        
        fr(i,n)
        {
            if(a[i]==st)
                count++;
            else
            {
                b[count]++;
                st=a[i];
                count=1;
            }
            if(i==n-1)
                b[count]++;

        }
        ll min=MAX_N;
        ll sum=0;
        // fr(i,n)
        //     cout<<b[i];
        fr(i,n+1)
        {
            if(b[i]!=0)
            {
            ll cur=sum;
            for(int j=i+1;j<=n;j++)
            {
                cur+=b[j]*(j-i);
            }
            // cout<<cur;
            if(cur<min)
                min=cur;
            sum+=b[i]*i;
        }
        }        
        cout<<min;
        cout<<endl;
}


   
    int main() {
        ios_base::sync_with_stdio(0);
        #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("error.txt", "w", stderr);
        freopen("output.txt", "w", stdout);
        #endif
        cin.tie(0); cout.tie(0);
    
        unsigned long long tc; cin>>tc;
        fr(t,tc) {
            // cout<<"Case #"<<t+1<<": ";
            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 <bits/stdc++.h>
    #include <string.h>
    using namespace std;
    
    #define ar array
    #define ll long long
    #define pb push_back
    #define fr(i,n) for(long long i=0;i<n;i++)
    
    const int MAX_N = 1e5 + 1;
    const int MOD = 1e9 + 7;
    const int INF = 1e9;
    const ll LINF = 1e18;
    ll power(ll x, ll y, ll M) {ll res = 1; while (y > 0) {if (y & 1) res = (res * x) % M; y >>= 1; x = (x * x) % M;} return res % M;}
    ll power(ll x, ll y) {ll res = 1; while (y > 0) {if (y & 1) res = (res * x); y >>= 1; x = (x * x);} return res;}
    
    bool sortcol( const vector<ll>& v1, const vector<ll>& v2 ) { 
 return v1[0] < v2[0]; 
} 

void sortArr(vector<pair<ll, ll> > & vp,ll v[], int n) 
            { 
    for (int i = 0; i < n; ++i) { 
        vp.push_back(make_pair(v[i], i)); 
    } 
  
    sort(vp.begin(), vp.end()); 
} 

int max(int a, int b) { return (a > b)? a : b; } 
int max(int a, int b, int c) { return max(max(a, b), c); }  
bool isPalindrome(string str)
{
    int j = str.length() - 1;

    for (int i = 0; i < j; i++, j--)
    {
        if (str[i] != str[j])
        {
            return false;
        }
    }

    return true;
}
void printDivisors(int n, std::vector<long> &v) 
{ 
    
    for (int i=1; i<=sqrt(n); i++) 
    { 
        if (n%i == 0) 
        { 
            
            if (n/i == i) 
                v.pb(i);  
            else 
            {
                v.pb(i);
                v.pb(n/i);
            }
        } 
    } 
} 
bool isPrime(int n) 
{ 
     
    if (n <= 1) 
        return false; 
    if (n <= 3) 
        return true; 
    if (n % 2 == 0 || n % 3 == 0) 
        return false; 
  
    for (int i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return false; 
  
    return true; 
} 


void solve() 
    {
        ll n;
        cin>>n;
        ll a[n];
        ll b[n+1];
        b[n]=0;
        fr(i,n)
        {
            cin>>a[i];
            b[i]=0;
        }
        sort(a,a+n);
        ll st=a[0];
        ll count=0;
        
        fr(i,n)
        {
            if(a[i]==st)
                count++;
            else
            {
                b[count]++;
                st=a[i];
                count=1;
            }
            if(i==n-1)
                b[count]++;

        }
        ll min=MAX_N;
        ll sum=0;
        // fr(i,n)
        //     cout<<b[i];
        fr(i,n+1)
        {
            if(b[i]!=0)
            {
            ll cur=sum;
            for(int j=i+1;j<=n;j++)
            {
                cur+=b[j]*(j-i);
            }
            // cout<<cur;
            if(cur<min)
                min=cur;
            sum+=b[i]*i;
        }
        }        
        cout<<min;
        cout<<endl;
}


   
    int main() {
        ios_base::sync_with_stdio(0);
        #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("error.txt", "w", stderr);
        freopen("output.txt", "w", stdout);
        #endif
        cin.tie(0); cout.tie(0);
    
        unsigned long long tc; cin>>tc;
        fr(t,tc) {
            // cout<<"Case #"<<t+1<<": ";
            solve();
        }
    }

```