#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 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
    }
    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 m = ceil(N/2)
        int m = (N + 1) / 2;
        
        // Find the maximum element in A to set upper_limit
        int max_A = 0;
        for(auto x : A) max_A = max(max_A, x);
        // To prevent memory issues, cap the upper_limit to 1e6
        int upper_limit = min(max_A, 1000000);
        
        // Initialize frequency array
        // Using vector<int> instead of array for dynamic sizing
        vector<int> freq(upper_limit + 1, 0);
        
        // Populate the frequency array with counts of divisors
        for(auto a : A){
            // Find all divisors of a up to upper_limit
            int sqrt_a = sqrt(a);
            for(int d = 1; d <= sqrt_a; ++d){
                if(a % d == 0){
                    if(d <= upper_limit){
                        freq[d]++;
                    }
                    int other = a / d;
                    if(other != d && other <= upper_limit){
                        freq[other]++;
                    }
                }
            }
        }
        
        // Initialize maximum sum
        long long max_sum = 0;
        
        // Iterate X from upper_limit down to 1
        for(int X = upper_limit; X >=1; --X){
            if(freq[X] >= m){
                // Assign m elements divisible by X to S1
                vector<int> S1;
                vector<int> S2;
                S1.reserve(m);
                S2.reserve(N - m);
                for(auto a : A){
                    if(a % X == 0 && (int)S1.size() < m){
                        S1.push_back(a);
                    }
                    else{
                        S2.push_back(a);
                    }
                }
                
                // Compute GCD of S2
                int Y;
                if(S2.empty()){
                    Y = 0; // Undefined, but set to 0
                }
                else{
                    Y = compute_gcd_list(S2);
                }
                
                // Compute sum
                long long current_sum = (long long)X + (long long)Y;
                if(current_sum > max_sum){
                    max_sum = current_sum;
                }
                
                // Since we're iterating from high to low, we can continue to find better sums
                // No early termination
            }
        }
        
        // Edge Case: If no X found (shouldn't happen as X=1 divides all)
        // But to be safe
        cout << max_sum << "\n";
    }
}