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

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define fo(i, b) for (int i = 0; i < (b); ++i)
#define F first
#define S second
#define MP make_pair
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

bool dfs(int a, int L, vector<vi> &g, vi &btoa, vi &A, vi &B)
{
	if (A[a] != L)
		return 0;
	A[a] = -1;
	for (int b : g[a])
		if (B[b] == L + 1)
		{
			B[b] = 0;
			if (btoa[b] == -1 || dfs(btoa[b], L + 1, g, btoa, A, B))
				return btoa[b] = a, 1;
		}
	return 0;
}

int hpcroftKarp(vector<vi> &g, vi &btoa)
{
	int res = 0;
	vi A(g.size()), B(btoa.size()), cur, next;
	for (;;)
	{
		fill(all(A), 0);
		fill(all(B), 0);
		cur.clear();
		for (int a : btoa)
			if (a != -1)
				A[a] = -1;
		rep(a, 0, sz(g)) if (A[a] == 0) cur.push_back(a);
		for (int lay = 1;; lay++)
		{
			bool islast = 0;
			next.clear();
			for (int a : cur)
				for (int b : g[a])
				{
					if (btoa[b] == -1)
					{
						B[b] = lay;
						islast = 1;
					}
					else if (btoa[b] != a && !B[b])
					{
						B[b] = lay;
						next.push_back(btoa[b]);
					}
				}
			if (islast)
				break;
			if (next.empty())
				return res;
			for (int a : next)
				A[a] = lay;
			cur.swap(next);
		}
		rep(a, 0, sz(g))
			res += dfs(a, 0, g, btoa, A, B);
	}
}

vector<bool> isPrime(100000, true);

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

	unordered_map<ll, ll> cnts;
	fo(lolol, n)
	{
		ll val;
		cin >> val;
		cnts[val]++;
	}

	vector<pll> cntvec(all(cnts));
	sort(all(cntvec));

	vector<vi> g;
	vi btoa;
	vi shadow;

	unordered_map<ll, ll> taken;

	for (auto [val, cnt] : cntvec)
	{
		ll good_cnt = 0;
		ll pos = val;

		fo(sgdgfdg, cnt)
			g.push_back({});

		while (good_cnt <= cnt + 2)
		{
			if (taken.count(pos) == 0 && isPrime[pos / val] && cnts.count(pos) == 0)
				good_cnt++;

			if (taken.count(pos) == 0)
			{
				taken[pos] = btoa.size();
				btoa.push_back(-1);
				shadow.push_back(pos);
			}

			rep(i, g.size() - cnt, g.size())
			{
				g[i].push_back(taken[pos]);
			}

			pos += val;
		}
	}

	ll mmin = 1;
	ll mmax = max_element(cntvec.begin(), cntvec.end())->F * n;

	while (mmax > mmin)
	{
		ll mid = (mmin + mmax) / 2;

		vector<vi> g2(g.size());

		fo(i, g.size())
		{
			for (ll val : g[i])
				if (shadow[val] <= mid)
					g2[i].push_back(val);
		}

		for (auto &v : btoa)
			v = -1;

		if (hpcroftKarp(g2, btoa) == g2.size())
			mmax = mid;
		else
			mmin = mid + 1;
	}

	cout << mmin << '\n';
}

signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	for (int i = 2; i < 100000; i++)
	{
		if (!isPrime[i])
			continue;

		for (int j = i * 2; j < 100000; j += i)
			isPrime[i] = false;
	}

	int t;
	cin >> t;
	fo(ttttttt, t)
	{
		solve();
	}
}