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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; 
    cin >> T;
    while(T--){
        int N;
        cin >> N;
        vector<int> A(N);
        int maxA = 0;
        for(int i = 0; i < N; i++){
            cin >> A[i];
            maxA = max(maxA, A[i]);
        }

        // how many we need in odd/even slots
        int kodd  = (N+1)/2;
        int keven = N/2;

        // frequency of values
        vector<int> freq(maxA+1, 0);
        for(int x: A) freq[x]++;

        // cnt[d] = # of A[i] divisible by d
        vector<int> cnt(maxA+1, 0);
        for(int d = 1; d <= maxA; d++){
            for(int m = d; m <= maxA; m += d)
                cnt[d] += freq[m];
        }

        // find best X, Y
        int bestX = 1;  // gcd at least 1 always possible
        for(int d = 1; d <= maxA; d++){
            if(cnt[d] >= kodd)
                bestX = d;
        }
        int bestY = 1;
        for(int d = 1; d <= maxA; d++){
            if(cnt[d] >= keven)
                bestY = d;
        }

        cout << (bestX + bestY) << "\n";
    }
    return 0;
}