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

// Function to calculate GCD of a list of numbers
int compute_gcd(const vector<int>& nums) {
    if (nums.empty()) return 0; // Undefined, but handled appropriately
    int result = nums[0];
    for(int i = 1; i < nums.size(); i++) {
        result = gcd(result, nums[i]);
        if(result == 1) break; // Early termination since GCD can't be lower than 1
    }
    return result;
}

int main(){
    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;
        
        // Determine the number of elements in Subset 1 (Odd positions)
        int m = (N + 1) / 2;
        int max_sum = 0;
        
        // Generate all combinations of m elements from N
        // Using bitmask: iterate from 0 to (1<<N)-1 and select those with exactly m bits set
        // Since N <=10, (1<<10)=1024, manageable
        for(int mask = 0; mask < (1<<N); mask++) {
            // Count number of set bits
            if(__builtin_popcount(mask) != m) continue;
            
            vector<int> subset1, subset2;
            for(int i = 0; i < N; i++) {
                if(mask & (1<<i)) subset1.push_back(A[i]);
                else subset2.push_back(A[i]);
            }
            
            // Compute GCDs
            int X = compute_gcd(subset1);
            int Y = compute_gcd(subset2);
            int current_sum = X + Y;
            
            if(current_sum > max_sum) {
                max_sum = current_sum;
            }
        }
        
        cout << max_sum << "\n";
    }
}