#include<iostream>
#include<algorithm>
#include<map>
#include<string>
#include<string.h>
#include<queue>
#include<deque>
#include<stack>
#include<utility>
using namespace std;
map<long long, int>vis;
int cnt[500000];
bool cmp(int x, int y)
{
		return x > y;
}
void solve()
{
	int n;
	cin >> n;
	memset(cnt, 0, sizeof(cnt));
	vis.clear();
	cnt[1] = 1;
	int count1 = 1;
	vis[0] = 1;
	for (int i = 2; i <= n; i++)
	{
		int x;
		cin >> x;
		if (!vis[x])
		{
			vis[x] = ++count1;
			cnt[vis[x]]++;
		}
		else
		{
			cnt[vis[x]]++;
		}
	}
	sort(cnt + 1, cnt + count1 + 1, cmp);
	for (int i = 1; i <= count1; i++)
	{
		cnt[i] -= count1 - i + 1;
	}
	int ans = count1;
	sort(cnt + 1, cnt + count1 + 1, cmp);
	long long sum = 0;
	int add = 0;
	for (int i = 1; i <= count1; i++)
	{
		if (cnt[i] <= 0)break;
		cnt[i] -= sum;
		if (cnt[i]>0)
		{
			if (cnt[i] >= add) { cnt[i] -= add; add = 0; }
			else
			{
				cnt[i] = 0;
				add -= cnt[i];
			}
		}
		if (cnt[i] <= 0) { continue; }
		if ((cnt[i] % 2) == 0)
		{
			sum += cnt[i] / 2;
		}
		else { sum += cnt[i] / 2 + 1; add++; }
	}
	cout << ans + sum << endl;
}
int main()
{
	std::ios::sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
}