#include<iostream>
#include<bits/stdc++.h>
using namespace std;

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)
#define DEB(x)	cout << #x << " " << x << endl;
#define DEB_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()
#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

typedef long long int LL;
typedef pair<int, int> PI;
typedef pair<LL, LL> PLL;
typedef vector<int> VI;
typedef vector<LL> VL;

void solve() {
	int n;
	cin >> n;

	map<int, int> mp;
	REP(i, n) {
		int x;
		cin >> x;
		mp[x]++;
	}

	vector<int> v;

	for (auto x: mp)
		v.push_back(x.second);

	sort(ALL(v));

	vector<LL> pref(v.size()+1);
	pref[0] = 0LL;
	REP(i, v.size())
		pref[i+1] = pref[i] + v[i];

	LL total = pref[v.size()];
	LL min_remove = total;

	REP(i, v.size()) {
		LL remove = pref[i];
		LL now_to_end_sum = total - pref[i];
		remove += now_to_end_sum - (LL)(v.size()-i) * v[i];
		CHMIN(min_remove, remove);
	}

	cout << min_remove << endl;	

}

int main() {

	IOS

	int t;
	cin >> t;

	while (t--) {
	    solve();
	}

	return 0;
}
### 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<iostream>
#include<bits/stdc++.h>
using namespace std;

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)
#define DEB(x)	cout << #x << " " << x << endl;
#define DEB_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()
#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

typedef long long int LL;
typedef pair<int, int> PI;
typedef pair<LL, LL> PLL;
typedef vector<int> VI;
typedef vector<LL> VL;

void solve() {
	int n;
	cin >> n;

	map<int, int> mp;
	REP(i, n) {
		int x;
		cin >> x;
		mp[x]++;
	}

	vector<int> v;

	for (auto x: mp)
		v.push_back(x.second);

	sort(ALL(v));

	vector<LL> pref(v.size()+1);
	pref[0] = 0LL;
	REP(i, v.size())
		pref[i+1] = pref[i] + v[i];

	LL total = pref[v.size()];
	LL min_remove = total;

	REP(i, v.size()) {
		LL remove = pref[i];
		LL now_to_end_sum = total - pref[i];
		remove += now_to_end_sum - (LL)(v.size()-i) * v[i];
		CHMIN(min_remove, remove);
	}

	cout << min_remove << endl;	

}

int main() {

	IOS

	int t;
	cin >> t;

	while (t--) {
	    solve();
	}

	return 0;
}
```