/*For today, you happen to be the defeated. But what will you become tomorrow?*/

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define int long long int 
#define dbg if(debugg)
#define F first 
#define S second 

bool debugg = false;

template <typename T>
using order_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;

template <typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());  


void solve()
{
    
    int n;
    cin >> n;
    vector<int>v(n);
    for(int i = 0; i < n; i ++) cin >> v[i];


    clock_t st = clock();
    int ans = 0;
    while(clock() < st + CLOCKS_PER_SEC * 1.5){
        random_shuffle(v.begin(), v.end());
        int x = 0, y = 0, a = (n + 1) / 2, b = n / 2;
        for(int i = 0; i < n; i ++){
            if(a == 0){
                y = __gcd(y, v[i]);
                b --;
            }
            else if(b == 0){
                x = __gcd(x, v[i]);
                a --;
            }

            else{
                if(__gcd(x, v[i]) == x){
                    a --;
                }

                else{
                    y = __gcd(y, v[i]);
                    b --;
                }
            }
        }
        ans = max(ans, x + y);

    }
    cout << ans << '\n';
}



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

    int t  = 1;
    cin>>t;

    while(t--){

        solve();

    }

    return 0;

}