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

using pi = pair<int, int>;
#define sz(x) int((x).size())
template<class F> struct Dinic {
    struct Edge {int to, rev; F cap;};
    int N; vector<vector<Edge>> adj;
    void init(int _N) {N = _N; adj.resize(N);}
    pi ae(int a, int b, F cap, F rcap = 0){
        assert(min(cap, rcap) >= 0);
        adj[a].push_back({b,sz(adj[b]),cap});
        adj[b].push_back({a,sz(adj[a])-1,rcap});
        return {a, sz(adj[a])-1};
    }
    vector<int> lev, ptr;
    bool bfs(int s, int t){
        lev = ptr = vector<int>(N);
        lev[s] = 1; queue<int> q({s});
        while(sz(q)){
            int u = q.front(); q.pop();
            for(auto &e: adj[u]) if(e.cap && !lev[e.to]){
                q.push(e.to), lev[e.to] = lev[u] + 1;
                if(e.to == t) return 1;
            }
        }
        return 0;
    }
    F dfs(int v, int t, F flo){
        if(v == t) return flo;
        for(int &i=ptr[v]; i<sz(adj[v]); i++){
            Edge &e = adj[v][i];
            if(lev[e.to] != lev[v] + 1 || !e.cap) continue;
            if(F df = dfs(e.to, t, min(flo, e.cap))){
                e.cap -= df;
                adj[e.to][e.rev].cap += df;
                return df;
            }
        }
        return 0;
    }
    F maxFlow(int s, int t){
        F tot = 0;
        while(bfs(s,t)) while(F df = dfs(s,t,numeric_limits<F>::max())) tot += df;
        return tot;
    }
};

#define int long long

void solve(){
    unordered_map<int, int> f;
    map<int,int> mp;


    int sum = 0;
    int n; cin >> n;
    for(int i=0; i<n; i++){
        int x; cin >> x;
        sum += x;
        f[x]++;
    }

    for(auto [a, b]: f){
        for(int i=1; i<=n; i++){
            mp[a*i]++;
        }
    }

    int ct = 0;
    for(auto [a, b]: mp){
        mp[a] = ct++;
    }


    auto check = [&](int k){

        Dinic<int> flow;
        flow.init(n*n + n + 2);

        int S = 0, T = 1;
        int UP = 2;
        int DOWN = n + 2;

        for(auto [a, b]: f){
            flow.ae(S, UP + mp[a], b);
            for(int i=1; i<=n; i++){
                if(a*i > k) break;
                flow.ae(UP + mp[a], DOWN + mp[a*i], 1);
            }
        }

        for(int i=0; i<ct; i++){
            flow.ae(DOWN + i, T, 1);
        }

        return flow.maxFlow(S, T) == n;
    };

    int l = 0, r = sum+1;

    while(r-l > 1){
        int m = (l+r)/2;

        if(check(m)) r = m;
        else l = m;
    }
    cout << r << "\n";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t; cin >> t;
    while(t--) solve();
}