#pragma GCC optimize("O3")
#include <bits/stdc++.h>

//#define int long long

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 pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

int cnt = 0;

int match(int u, vector<int> &vis, vector<vector<int>> &graph, vector<int> &ntot, vector<int> &tton, int max_ind){
	for(int v : graph[u]) if(vis[v] < cnt){
		if(v > max_ind) break;
		if(tton[v] == -1){
			tton[v] = u;
			ntot[u] = v;
			return 1;
		}
	}
	for(int v : graph[u]) if(vis[v] < cnt){
		if(v > max_ind) break;
		vis[v] = cnt;
		if(match(tton[v],vis,graph,ntot,tton,max_ind)){
			tton[v] = u;
			ntot[u] = v;
			return 1;
		}
	}
	return 0;
}

int can(int n, vector<int> &nodes, int max_ind, vector<ll> &times, vector<vector<int>> &graph){ // important to copy comb
	vector<int> vis(sz(times)), ntot(sz(nodes),-1), tton(sz(times),-1);
	for(int i = sz(nodes)-1; i >= 0; i--){
		for(int v : graph[i]){
			if(v > max_ind) break;
			if(tton[v] == -1){
				tton[v] = i;
				ntot[i] = v;
				break;
			}
		}
	}
	bool change = true;
	while(change){
		change = false;
		cnt++;
		for(int i = sz(nodes)-1; i >= 0; i--) if(ntot[i] == -1){
			change |= match(i,vis,graph,ntot,tton,max_ind);
		}
	}
	for(int x : ntot) if(x == -1) return false;
	return true;
}

void solve(){
	int n;
	cin >> n;
	vector<int> a;
	set<ll> used;
	int sol = 0;
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		if(used.count(x)) a.push_back(x);
		else{
			used.insert(x);
			sol = max(sol,x);
		}
	}
	sort(all(a));
	int m = sz(a);
	//cerr << "wtf" << endl;
	if(m == 0){
		cout << sol << "\n";
		return;
	}
	map<int,int> comb;
	for(int x : a) comb[x]++;
	vector<ll> times;
	for(auto [x,y] : comb){
		for(int i = 0; i < n; i++) if(!used.count(x*(ll)(i+1))) times.push_back(x*(ll)(i+1));
	}
	sort(all(times));
	times.resize(unique(all(times))-times.begin());
	vector<int> nodes;
	for(auto [x,y] : comb){
		while(y--) nodes.push_back(x);
	}
	vector<vector<int>> graph(sz(nodes));
	for(int i = 0; i < sz(nodes); i++){
		for(int j = 1; j <= n; j++) if(!used.count(j*(ll)nodes[i])){
			int ind = lower_bound(all(times),j*(ll)nodes[i])-begin(times);
			if(ind < sz(times) && times[ind] == j*(ll)nodes[i]) graph[i].push_back(ind);
		}
	}
	int l = max(m-1,(int)(upper_bound(times.begin(),times.end(),(ll)sol)-times.begin()-1)), r = sz(times)-1;
	while(l < r){
//		cerr << "bs" << endl;
		int mid = (l+r)/2;
		if(can(n,nodes,mid,times,graph)) r = mid;
		else l = mid+1;
	}
	cout << max((ll)sol,times[l]) << "\n";
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	int t;
	cin >> t;
	while(t--) solve();
}