#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];
   }

   vector<vector<int>>x(101, vector<int>(101,0));
   vector<vector<int>> y = x;

   for(int i = 0; i < n; i++){
      vector<int> d;
      for(int j = 1; j * j <= a[i]; j++){
         if(a[i] % j == 0){
            d.push_back(j);
            if(a[i] / j != j)d.push_back(a[i] / j);
         }
      }
      sort(d.begin(), d.end());

      for(auto it : d){
         for(auto it1 : d){
            x[it][it1]++;
         }
      }

      for(auto x : d){
         for(int j = 1; j <= 100; j++){
            if(a[i] % j == 0)continue;
            y[x][j]++;
         }
      }
   }


   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 = x[i][j];
         if(i != j){
            o = y[i][j], e = y[j][i];
         }
         
         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;
}