#include<cstdio>
#include<algorithm>
#include<ctype.h>
#define int long long

using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f; 
}

int t,n,a[200005],b[200005],c[200005],tot,sum[200005];

int query(int k)
{
	int l=1,r=tot,ret;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(c[mid]>=k)ret=mid,r=mid-1;
		else l=mid+1;
	}
	return ret;
}

signed main()
{
	t=read();
	while(t--)
	{
		n=read();tot=0;
		for(int i=1;i<=n;i++)
			a[i]=b[i]=read();
		sort(b+1,b+n+1);
		for(int i=1;i<=n;i++)
		{
			if(i==1||b[i]!=b[i-1])
				c[++tot]=b[i];
			b[i-1]=0;
		}
		b[n]=0;
		int sum1=0,sum2=0,ans=0;
		for(int i=1;i<=n;i++)
			a[i]=query(a[i]);
		
		for(int i=1;i<=n;i++)
			b[a[i]]++;
		sort(b+1,b+tot+1);
		for(int i=1;i<=n;i++)
			sum[i]=sum[i-1]+b[i];
		ans=n;
		for(int i=1;i<=n;i++)
		{
			int l=1,r=tot,now=0x3f3f3f3f;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(b[mid]>=i)now=mid,r=mid-1;
				else l=mid+1;
			}
			if(now==0x3f3f3f3f);
			else ans=min(ans,sum[now-1]+(sum[tot]-sum[now-1]-(tot-now+1)*i));
		}
		printf("%lld\n",ans);
	}
 } 
### Prompt

Please create a solution in Cpp to 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<cstdio>
#include<algorithm>
#include<ctype.h>
#define int long long

using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f; 
}

int t,n,a[200005],b[200005],c[200005],tot,sum[200005];

int query(int k)
{
	int l=1,r=tot,ret;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(c[mid]>=k)ret=mid,r=mid-1;
		else l=mid+1;
	}
	return ret;
}

signed main()
{
	t=read();
	while(t--)
	{
		n=read();tot=0;
		for(int i=1;i<=n;i++)
			a[i]=b[i]=read();
		sort(b+1,b+n+1);
		for(int i=1;i<=n;i++)
		{
			if(i==1||b[i]!=b[i-1])
				c[++tot]=b[i];
			b[i-1]=0;
		}
		b[n]=0;
		int sum1=0,sum2=0,ans=0;
		for(int i=1;i<=n;i++)
			a[i]=query(a[i]);
		
		for(int i=1;i<=n;i++)
			b[a[i]]++;
		sort(b+1,b+tot+1);
		for(int i=1;i<=n;i++)
			sum[i]=sum[i-1]+b[i];
		ans=n;
		for(int i=1;i<=n;i++)
		{
			int l=1,r=tot,now=0x3f3f3f3f;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(b[mid]>=i)now=mid,r=mid-1;
				else l=mid+1;
			}
			if(now==0x3f3f3f3f);
			else ans=min(ans,sum[now-1]+(sum[tot]-sum[now-1]-(tot-now+1)*i));
		}
		printf("%lld\n",ans);
	}
 } 
```