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

#define print(a) for(auto x:a)cout<<x<<' ';cout<<'\n';
#define debug(x) cout<<#x<<" "<<x<<'\n'
#define int   long long int

const int M = 1e9 + 7;
const int N = 2e5 + 10;

void solve(){
   int n; cin >> n;
   vector<int> a(n);

   for(int i = 0; i < n; i++){
      cin >> a[i];
   }
   int res = 0;

   int even = n / 2, odd = (n + 1) / 2;

   for(int i = 1; i <= 100; i++){
      for(int j = 1; j <= 100; j++){
         int o = 0, e = 0, both = 0;
         for(int k = 0; k < n; k++){
            if(a[k] % i == 0 && a[k] % j == 0)both++;
            else if(a[k] % i == 0)e++;
            else if(a[k] % j == 0)o++;
         }
         int mn = max(0ll, min(both, even - e));
         both -= mn;
         e += mn;
         o += both;
         if(e == even && o == odd)res = max(res, i + j);
      }
   }

   cout << res << '\n';
}


signed main() {
   ios_base::sync_with_stdio (0);
   cin.tie (0);

   int t = 1;   cin >> t;
   for (int tc = 1; tc <= t; tc++) {
      //cout<<"Case "<<tc<<": ";
      solve();
   }
   return 0;
}