// O(2 ^ N * (N ^ 2))

// Love the way you Lie.

#include <bits/stdc++.h>

using namespace std;

int n;
int dp[1 << 20];
vector<int> a;

int go(int mask) {
	int used = __builtin_popcount(mask);
	// array becomes empty
	if (used == n) {
		return 0;
	}
	// memoize
	if (dp[mask] != -1) {
		return dp[mask];
	}
	int cur_move = used / 2 + 1;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (!(mask >> i & 1) && !(mask >> j & 1)) {
				int points = __gcd(a[i], a[j]) * cur_move;
				int rem = go(mask | (1 << i) | (1 << j));
				ans = max(ans, rem + points);
			}
		}
	}
	return dp[mask] = ans;
}


void solve() {
	cin >> n;
	memset(dp, -1, sizeof dp);
	a.resize(n);
	assert(n % 2 == 0);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}	
	cout << go(0);
}

#define single_test

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1;
    #ifndef single_test
        cin >> t;
    #endif
    for (int i = 1; i <= t; ++i) {
        // cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}