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

#define all(v) v.begin(), v.end()

using LL = long long;

const int N = 1001;

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 = 1; 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 = min (left + 1, even);
          else if (v[k] % j == 0) right = min (right + 1, odd);
        }
        if (left + right + both == n) ans = max (ans, i + j);
      }
    }
    cout << ans << '\n';
  }

  return 0;
}