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

// Function to compute GCD of two numbers
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

// Function to compute GCD of an array
int array_gcd(vector<int> &arr)
{
    int result = arr[0];
    for (int i = 1; i < arr.size(); i++)
    {
        result = gcd(result, arr[i]);
    }
    return result;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int> A(n);
        for (int i = 0; i < n; i++)
        {
            cin >> A[i];
        }

        // Separate odd and even indexed elements
        vector<int> odd_elements, even_elements;
        for (int i = 0; i < n; i++)
        {
            if (i % 2 == 0)
            {
                even_elements.push_back(A[i]);
            }
            else
            {
                odd_elements.push_back(A[i]);
            }
        }

        // Compute initial GCDs
        int odd_gcd = array_gcd(odd_elements);
        int even_gcd = array_gcd(even_elements);

        // Initial maximum sum of GCDs
        int max_sum = odd_gcd + even_gcd;

        // Try to optimize by swapping elements
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                swap(A[i], A[j]);

                // Recompute GCDs after swapping
                odd_elements.clear();
                even_elements.clear();
                for (int k = 0; k < n; k++)
                {
                    if (k % 2 == 0)
                    {
                        even_elements.push_back(A[k]);
                    }
                    else
                    {
                        odd_elements.push_back(A[k]);
                    }
                }

                int new_odd_gcd = array_gcd(odd_elements);
                int new_even_gcd = array_gcd(even_elements);
                int new_sum = new_odd_gcd + new_even_gcd;

                // Update maximum sum if new sum is greater
                if (new_sum > max_sum)
                {
                    max_sum = new_sum;
                }

                // Swap back to original configuration
                swap(A[i], A[j]);
            }
        }

        // Output the maximum possible sum of GCDs
        cout << max_sum << endl;
    }

    return 0;
}