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

// Function to compute GCD of a list of numbers
int compute_gcd_list(const vector<int>& nums) {
    if (nums.empty()) return 0; // Undefined, but set to 0
    int result = nums[0];
    for(int i = 1; i < nums.size(); ++i){
        result = gcd(result, nums[i]);
        if(result ==1) break; // Early termination if GCD becomes 1
    }
    return result;
}

void solve(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    while(T--){
        int N;
        cin >> N;
        vector<int> A(N);
        for(auto &x : A) cin >> x;
        // Calculate m = ceil(N / 2)
        int m = (N +1)/2;
        // Find the maximum element in A
        int max_A = 0;
        for(auto x : A) max_A = max(max_A, x);
        // Build frequency array
        // To handle large max_A efficiently, use vector<int> with size max_A +1
        // Initialize all frequencies to 0
        vector<int> freq(max_A +1, 0);
        for(auto x : A) freq[x]++;
        // Initialize maximum sum
        long long max_sum = 0;
        // Iterate Y from max_A down to1
        for(int Y = max_A; Y >=1; Y--){
            // Count the number of elements divisible by Y
            int count_Y =0;
            for(int k=1; k * Y <=max_A; k++){
                count_Y += freq[k * Y];
            }
            // If at least (N - m) elements are divisible by Y
            if(count_Y >= (N - m)){
                // Assign S2 as the first (N - m) elements divisible by Y
                vector<int> S2;
                vector<int> S1;
                S2.reserve(N - m);
                S1.reserve(m);
                for(auto x : A){
                    if(x % Y ==0 && (int)S2.size() < (N - m)){
                        S2.push_back(x);
                    }
                    else{
                        S1.push_back(x);
                    }
                }
                // Compute GCD of S1
                int X = compute_gcd_list(S1);
                // Compute sum X + Y
                long long current_sum = (long long)X + (long long)Y;
                // Update maximum sum if necessary
                if(current_sum > max_sum){
                    max_sum = current_sum;
                }
            }
        }
        // Output the maximum sum for the current test case
        cout << max_sum << "\n";
    }
}

int main(){
    solve();
}