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

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

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

    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<int> A(N);
        for (int i = 0; i < N; i++) {
            cin >> A[i];
        }
        int k1 = (N + 1) / 2;
        int k2 = N / 2;
        
        // dp holds encoded states (cnt1, g1, g2)
        unordered_set<int> dp, nxt;
        dp.reserve(100000);
        nxt.reserve(100000);
        // encode: key = (cnt1 * 101 + g1) * 101 + g2
        auto encode = [&](int cnt1, int g1, int g2) {
            return (cnt1 * 101 + g1) * 101 + g2;
        };
        auto decode = [&](int key, int &cnt1, int &g1, int &g2) {
            g2 = key % 101;
            key /= 101;
            g1 = key % 101;
            cnt1 = key / 101;
        };

        // initial state: cnt1=0, g1=0, g2=0
        dp.insert(encode(0, 0, 0));

        for (int i = 0; i < N; i++) {
            nxt.clear();
            for (int key : dp) {
                int cnt1, g1, g2;
                decode(key, cnt1, g1, g2);
                int cnt2 = i - cnt1;
                // assign A[i] to group1 if possible
                if (cnt1 < k1) {
                    int ng1 = (g1 == 0 ? A[i] : gcd(g1, A[i]));
                    nxt.insert(encode(cnt1 + 1, ng1, g2));
                }
                // assign A[i] to group2 if possible
                if (cnt2 < k2) {
                    int ng2 = (g2 == 0 ? A[i] : gcd(g2, A[i]));
                    nxt.insert(encode(cnt1, g1, ng2));
                }
            }
            dp.swap(nxt);
        }

        int ans = 0;
        for (int key : dp) {
            int cnt1, g1, g2;
            decode(key, cnt1, g1, g2);
            if (cnt1 == k1) {
                ans = max(ans, g1 + g2);
            }
        }
        cout << ans;
        if (T) cout << '\n';
    }

    return 0;
}