//Date:16-02-2021 //Author: Rishabh Paul

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

// void run_case() {
// 	int n;
// 	cin >> n;
// 	int p, x;
// 	cin >> p;
// 	int ans = 0;
// 	for (int i = 1; i < n; i++) {
// 		cin >> x;
// 		int mi = min(p, x), mx = max(p, x);
// 		while(mx > 2 * mi) {
// 			ans++;
// 			mi = min(2 * mi, mx);
// 			mx = max(2 * mi, mx);
// 		}
// 		p = x;
// 	}
// 	cout << ans << "\n";
// }


// void run_case() {
// 	int n, x;
// 	cin >> n;
// 	vector<int> a(n), sum(3, 0);
// 	for(int i = 0; i < n; i++) {
// 		cin >> a[i];
// 		a[i] %= 3;
// 		sum[a[i]]++;
// 	}
// 	int ans = 0, r = n / 3;
// 	for(int i = 0; i < n; i++) {
// 		if (sum[a[i]] < r) continue;
// 		if (sum[a[i]] == r) continue;
// 		sum[a[i]]--;
// 		if (sum[(a[i] + 1)%3] < r) {
// 			ans++;
// 			sum[(a[i] + 1)%3]++;
// 			a[i] = (a[i] + 1)%3;
// 			continue;
// 		}
// 		if (sum[(a[i] + 2)%3] < r) {
// 			ans+=2;
// 			sum[(a[i] + 2)%3]++;
// 			a[i] = (a[i] + 2)%3;
// 		}
// 	}
// 	cout << ans << "\n";
// }


// void run_case() {
// 	long long x;
// 	cin >> x;
// 	const long long N = 1e4;
// 	long long a, b;
// 	long long lo, hi, m, cu;
// 	bool found = false;
// 	for(long long a = 1; a <= N; a++) {
// 		if (a * a * a >= x) break;
// 		b = x - a * a * a;
// 		lo = 1, hi = min(b, N);
// 		while(lo <= hi) {
// 			m = (lo + hi) / 2;
// 			cu = m * m * m;
// 			if (cu == b) {
// 				found = true; break;
// 			} else if (cu > b) hi = m - 1;
// 			else lo = m + 1;
// 		}
// 		if (found) break;
// 	}
// 	puts(found ? "yes": "no");
// }

// void dfs(int i, int j, vector<int> &a, int pDepth, vector<int> &ans) {
// 	if (i > j) return;
// 	int mx = 0, mxIndex;
// 	for(int k = i; k <= j; k++) {
// 		if (a[k] > mx) {
// 			mx = a[k];
// 			mxIndex = k;
// 		}
// 	}
// 	ans[mxIndex] = pDepth + 1;
// 	if (mxIndex > i) {
// 		dfs(i, mxIndex - 1, a, pDepth + 1, ans);
// 	}
// 	if (mxIndex < j) {
// 		dfs(mxIndex + 1, j, a, pDepth + 1, ans);
// 	}
// }

// void run_case() {
// 	int n;
// 	cin >> n;
// 	vector<int> a(n), ans(n);
// 	for(int i = 0; i < n; i++) cin >> a[i];
// 	dfs(0, n - 1, a, -1, ans);
// 	for(auto x: ans) cout << x << " "; cout << "\n";
// }

void run_case() {
	int n;
	cin >> n;
	vector<int> a(n);
	map<int, int> m;
	map<int, int> occur;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		m[a[i]]++;
	}
	for(auto x: m) {
		occur[x.second]++;
	}
	int ans = INT_MAX, mx, t, md;
	for(auto x: occur) {
		mx = 0;
		md = x.first;
		// cout << md << "\n";
		for(auto y: m) {
			t = y.second;
			// cout << t << " ";
			if (t > md) mx += t - md;
			else if (t < md) {
				mx += t;
			}
		}
		// cout << "\n-----------------------\n";
		ans = min(ans, mx);
	}
	cout << ans << "\n";
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int T;
	cin >> T;
	while(T--) {
		run_case();
	}
	return 0;
}

### 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
//Date:16-02-2021 //Author: Rishabh Paul

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

// void run_case() {
// 	int n;
// 	cin >> n;
// 	int p, x;
// 	cin >> p;
// 	int ans = 0;
// 	for (int i = 1; i < n; i++) {
// 		cin >> x;
// 		int mi = min(p, x), mx = max(p, x);
// 		while(mx > 2 * mi) {
// 			ans++;
// 			mi = min(2 * mi, mx);
// 			mx = max(2 * mi, mx);
// 		}
// 		p = x;
// 	}
// 	cout << ans << "\n";
// }


// void run_case() {
// 	int n, x;
// 	cin >> n;
// 	vector<int> a(n), sum(3, 0);
// 	for(int i = 0; i < n; i++) {
// 		cin >> a[i];
// 		a[i] %= 3;
// 		sum[a[i]]++;
// 	}
// 	int ans = 0, r = n / 3;
// 	for(int i = 0; i < n; i++) {
// 		if (sum[a[i]] < r) continue;
// 		if (sum[a[i]] == r) continue;
// 		sum[a[i]]--;
// 		if (sum[(a[i] + 1)%3] < r) {
// 			ans++;
// 			sum[(a[i] + 1)%3]++;
// 			a[i] = (a[i] + 1)%3;
// 			continue;
// 		}
// 		if (sum[(a[i] + 2)%3] < r) {
// 			ans+=2;
// 			sum[(a[i] + 2)%3]++;
// 			a[i] = (a[i] + 2)%3;
// 		}
// 	}
// 	cout << ans << "\n";
// }


// void run_case() {
// 	long long x;
// 	cin >> x;
// 	const long long N = 1e4;
// 	long long a, b;
// 	long long lo, hi, m, cu;
// 	bool found = false;
// 	for(long long a = 1; a <= N; a++) {
// 		if (a * a * a >= x) break;
// 		b = x - a * a * a;
// 		lo = 1, hi = min(b, N);
// 		while(lo <= hi) {
// 			m = (lo + hi) / 2;
// 			cu = m * m * m;
// 			if (cu == b) {
// 				found = true; break;
// 			} else if (cu > b) hi = m - 1;
// 			else lo = m + 1;
// 		}
// 		if (found) break;
// 	}
// 	puts(found ? "yes": "no");
// }

// void dfs(int i, int j, vector<int> &a, int pDepth, vector<int> &ans) {
// 	if (i > j) return;
// 	int mx = 0, mxIndex;
// 	for(int k = i; k <= j; k++) {
// 		if (a[k] > mx) {
// 			mx = a[k];
// 			mxIndex = k;
// 		}
// 	}
// 	ans[mxIndex] = pDepth + 1;
// 	if (mxIndex > i) {
// 		dfs(i, mxIndex - 1, a, pDepth + 1, ans);
// 	}
// 	if (mxIndex < j) {
// 		dfs(mxIndex + 1, j, a, pDepth + 1, ans);
// 	}
// }

// void run_case() {
// 	int n;
// 	cin >> n;
// 	vector<int> a(n), ans(n);
// 	for(int i = 0; i < n; i++) cin >> a[i];
// 	dfs(0, n - 1, a, -1, ans);
// 	for(auto x: ans) cout << x << " "; cout << "\n";
// }

void run_case() {
	int n;
	cin >> n;
	vector<int> a(n);
	map<int, int> m;
	map<int, int> occur;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		m[a[i]]++;
	}
	for(auto x: m) {
		occur[x.second]++;
	}
	int ans = INT_MAX, mx, t, md;
	for(auto x: occur) {
		mx = 0;
		md = x.first;
		// cout << md << "\n";
		for(auto y: m) {
			t = y.second;
			// cout << t << " ";
			if (t > md) mx += t - md;
			else if (t < md) {
				mx += t;
			}
		}
		// cout << "\n-----------------------\n";
		ans = min(ans, mx);
	}
	cout << ans << "\n";
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int T;
	cin >> T;
	while(T--) {
		run_case();
	}
	return 0;
}

```