#include<iostream>
#include<math.h>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define MOD 1000000007
#define f(i,a,b) for(int i=a;i<b;i++)
#define fe(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=b;i>a;i--)
#define fde(i,a,b) for(int i=b;i>=a;i--)
#define fastio cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define F first
#define S second
#define mp make_pair
#define epsilon 1e-15
#define pb push_back
#define PI 3.1415926535897932384626433832
using namespace std;
ll power(ll a,ll b,ll mod)
{
        ll res=1;
        a%=mod;
        while(b>0)
        {
                if(b&1)
                res=(res*a)%mod;

                a=(a*a)%mod;
                b>>=1;

        }
        return res;
}

ll fact[200001]={0};
ll invfact[200001]={0};

ll facto(ll mod)
{
        fact[0]=1;
        fact[1]=1;
        for(int i=2;i<=200000;++i)
        fact[i]=(i*fact[i-1])%mod;
        
        for(int i=0;i<=200000;++i)
        {
                invfact[i]=power(fact[i],mod-2,mod);
        }
}
ll ncr(ll a,ll b,ll mod)
{
        if(a<b)
        return 0;

        

        ll ans=1;
        ans=(ans*fact[a]);
        ans=(ans*invfact[a-b])%mod;
        ans=(ans*invfact[b])%mod;

        return ans;
   
}
int ans[500]={0};
void rec(int *arr,int l,int r,int cnt)
{
        if(l>r)
        return ;

        int maxi=-1;
        int maxpos=-1;
        for(int i=l;i<=r;++i)
        {
                if(arr[i]>maxi)
                {
                        maxi=arr[i];
                        maxpos=i;
                }
        }
        ans[maxpos]=cnt;
        rec(arr,l,maxpos-1,cnt+1);
        rec(arr,maxpos+1,r,cnt+1);


}

int main()
{
        int tc;
        cin>>tc;
        
        while(tc--)
        {
                int n;
                cin>>n;
                int arr[n];
                for(auto &i:arr) cin>>i;
                map<int,int>m1;
                for(auto it:arr) m1[it]++;
                map<int,int>m2;
                for(auto it:m1)
                m2[it.S]++;

                vector<pair<int,int> >v;
                for(auto it:m2)
                {
                        v.pb(it);
                }
                sort(v.begin(),v.end());
                int mini=n;
                int cnt=0,a=0,b=0;
                for(int i=v.size()-1;i>=0;--i)
                {
                        cnt+=(v[i].F*v[i].S);
                        if(i!=v.size()-1)
                        a+=b*(v[i+1].F-v[i].F);

                        b+=v[i].S;
                        int temp=n-cnt+a;
                        if(temp<mini)
                        mini=temp;

                }
                cout<<mini<<"\n";



        }
        



        
        
}
### Prompt

Create a solution in Cpp for 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<math.h>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define MOD 1000000007
#define f(i,a,b) for(int i=a;i<b;i++)
#define fe(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=b;i>a;i--)
#define fde(i,a,b) for(int i=b;i>=a;i--)
#define fastio cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define F first
#define S second
#define mp make_pair
#define epsilon 1e-15
#define pb push_back
#define PI 3.1415926535897932384626433832
using namespace std;
ll power(ll a,ll b,ll mod)
{
        ll res=1;
        a%=mod;
        while(b>0)
        {
                if(b&1)
                res=(res*a)%mod;

                a=(a*a)%mod;
                b>>=1;

        }
        return res;
}

ll fact[200001]={0};
ll invfact[200001]={0};

ll facto(ll mod)
{
        fact[0]=1;
        fact[1]=1;
        for(int i=2;i<=200000;++i)
        fact[i]=(i*fact[i-1])%mod;
        
        for(int i=0;i<=200000;++i)
        {
                invfact[i]=power(fact[i],mod-2,mod);
        }
}
ll ncr(ll a,ll b,ll mod)
{
        if(a<b)
        return 0;

        

        ll ans=1;
        ans=(ans*fact[a]);
        ans=(ans*invfact[a-b])%mod;
        ans=(ans*invfact[b])%mod;

        return ans;
   
}
int ans[500]={0};
void rec(int *arr,int l,int r,int cnt)
{
        if(l>r)
        return ;

        int maxi=-1;
        int maxpos=-1;
        for(int i=l;i<=r;++i)
        {
                if(arr[i]>maxi)
                {
                        maxi=arr[i];
                        maxpos=i;
                }
        }
        ans[maxpos]=cnt;
        rec(arr,l,maxpos-1,cnt+1);
        rec(arr,maxpos+1,r,cnt+1);


}

int main()
{
        int tc;
        cin>>tc;
        
        while(tc--)
        {
                int n;
                cin>>n;
                int arr[n];
                for(auto &i:arr) cin>>i;
                map<int,int>m1;
                for(auto it:arr) m1[it]++;
                map<int,int>m2;
                for(auto it:m1)
                m2[it.S]++;

                vector<pair<int,int> >v;
                for(auto it:m2)
                {
                        v.pb(it);
                }
                sort(v.begin(),v.end());
                int mini=n;
                int cnt=0,a=0,b=0;
                for(int i=v.size()-1;i>=0;--i)
                {
                        cnt+=(v[i].F*v[i].S);
                        if(i!=v.size()-1)
                        a+=b*(v[i+1].F-v[i].F);

                        b+=v[i].S;
                        int temp=n-cnt+a;
                        if(temp<mini)
                        mini=temp;

                }
                cout<<mini<<"\n";



        }
        



        
        
}
```