#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define vvi             vector<vector<int>>
#define ld              long double
#define mod             1000000007
#define ff              first
#define ss              second
#define int            	long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vpii            vector<pair<int,int>>
#define all(x)          x.begin(),x.end()
#define sz(a)           (int)(a.size())
#define vi              vector<int>
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define SS              stringstream
#define db(...)         __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << '\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');
	cerr.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}


// const int dirx[4] = {0, 0, -1, 1};
// const int diry[4] = { -1, 1, 0, 0};

// 0 -> l, 1 - > r, 2 -> u , 3 -> down

void FASTIO()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

const int mxN = 2e5 + 100;
int a[mxN];
int ans[mxN];
int in[mxN];
int n, k, q;
string s;

void test_case()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];

	sort(a + 1, a + n + 1);

	map<int,int> m;
	for(int i = 1; i <= n; i++)
		m[a[i]]++;

	vi v;
	for(auto it : m)
		v.pb(it.ss);

	if(sz(v) == 1)
	{
		cout << 0 << '\n';
		return;
	}

	sort(all(v));

	if(sz(v) == 2)
	{
		cout << min(v[0], v[1] - v[0]) << '\n';
		return;
	}

	n = sz(v);

	vi pre(n, 0);
	pre[0] = v[0];

	vi suf(n, 0);
	suf[n - 1] = v[n - 1];

	for(int i = 1; i < n; i++)
		pre[i] = pre[i - 1] + v[i];

	for(int i = n - 2; i >= 0; i--)
		suf[i] = suf[i + 1] + v[i];

	int ans = 1e18;	

	for(int i = 0; i < n; i++)
	{
		int pehle = 0;
		if(i > 0)
			pehle = pre[i - 1];

		int baad = 0;
		if(i < n - 1)
			baad = suf[i + 1] - (n - 1 - (i + 1) + 1) * v[i];
		
		ans = min(ans, pehle + baad);
	}

	cout << ans << '\n';
}

int32_t main()
{
	FASTIO();

	int t;
	t = 1;
	cin >> t;

	for (int i = 1; i <= t; i++)
	{
		//cout << "Case #" << i << ": ";
		test_case();
	}
	return 0;
}
### Prompt

Your challenge is to write a CPP solution 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 <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define vvi             vector<vector<int>>
#define ld              long double
#define mod             1000000007
#define ff              first
#define ss              second
#define int            	long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vpii            vector<pair<int,int>>
#define all(x)          x.begin(),x.end()
#define sz(a)           (int)(a.size())
#define vi              vector<int>
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define SS              stringstream
#define db(...)         __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << '\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');
	cerr.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}


// const int dirx[4] = {0, 0, -1, 1};
// const int diry[4] = { -1, 1, 0, 0};

// 0 -> l, 1 - > r, 2 -> u , 3 -> down

void FASTIO()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

const int mxN = 2e5 + 100;
int a[mxN];
int ans[mxN];
int in[mxN];
int n, k, q;
string s;

void test_case()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];

	sort(a + 1, a + n + 1);

	map<int,int> m;
	for(int i = 1; i <= n; i++)
		m[a[i]]++;

	vi v;
	for(auto it : m)
		v.pb(it.ss);

	if(sz(v) == 1)
	{
		cout << 0 << '\n';
		return;
	}

	sort(all(v));

	if(sz(v) == 2)
	{
		cout << min(v[0], v[1] - v[0]) << '\n';
		return;
	}

	n = sz(v);

	vi pre(n, 0);
	pre[0] = v[0];

	vi suf(n, 0);
	suf[n - 1] = v[n - 1];

	for(int i = 1; i < n; i++)
		pre[i] = pre[i - 1] + v[i];

	for(int i = n - 2; i >= 0; i--)
		suf[i] = suf[i + 1] + v[i];

	int ans = 1e18;	

	for(int i = 0; i < n; i++)
	{
		int pehle = 0;
		if(i > 0)
			pehle = pre[i - 1];

		int baad = 0;
		if(i < n - 1)
			baad = suf[i + 1] - (n - 1 - (i + 1) + 1) * v[i];
		
		ans = min(ans, pehle + baad);
	}

	cout << ans << '\n';
}

int32_t main()
{
	FASTIO();

	int t;
	t = 1;
	cin >> t;

	for (int i = 1; i <= t; i++)
	{
		//cout << "Case #" << i << ": ";
		test_case();
	}
	return 0;
}
```