#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using LL = long long;
const int N = 101;
int main() {
cin.tie (nullptr) -> ios_base :: sync_with_stdio (false);
int tests;
cin >> tests;
while (tests--) {
int n;
cin >> n;
vector <int> v (n);
for (auto &i : v) cin >> i;
int even = n / 2, odd = n - even, ans = 0;
for (int i = 1; i <= N; i++) {
for (int j = i; j <= N; j++) {
int both = 0, left = 0, right = 0;
for (int k = 0; k < n; k++) {
if (v[k] % (i * j) == 0) both++;
else if (v[k] % i == 0) left++;
else if (v[k] % j == 0) right++;
}
if (left > right) swap (left, right);
if (both >= max (0, even - left) + max (0, odd - right)) ans = max (ans, i + j);
}
}
cout << ans << '\n';
}
return 0;
}