#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
      long long n;
      cin>>n;
      vector<long long>v(n);
      for(int i=0;i<n;i++)
      {
          cin>>v[i];
      }

      sort(v.begin(),v.end());
      reverse(v.begin(),v.end());

      long long odd=n/2;

      if(n%2!=0)
        odd++;

        long long even=n/2;

        long long anse=1;
        long long anso=1;


        for(int i=105;i>=1;i--)
        {
            long long cnt=0;
            for(int j=0;j<n;j++)
            {
                if(v[j]%i==0)
                cnt++;


            }

            if(cnt>=odd&&i>anso)
            {
                //anso+=i;
               // anso=max(anso,i);
               anso=i;
                cnt-=odd;

            }

            if(cnt>=even&&i>anse)
            {
                anse=i;
                cnt-=even;
            }
        }

        cout<<anse+anso<<endl;

       /* long long maxxo=1;

      for(int i=0;i<n;i++)
      {
          long long gcdd=v[i];

          long long check=0;

          for(int j=0;j<n;j++)
          {
              if(check>=odd)
                break;
              if(i==j)
                continue;

                long long temp=__gcd(v[j],gcdd);
                if(temp!=1)
                {
                    check++;
                    gcdd=temp;

                }
          }

          if(check>=odd)
          {
              maxxo=max(maxxo,gcdd);
          }
      }



      long long maxxe=1;

      for(int i=0;i<n;i++)
      {
          long long gcdd=v[i];

          long long check=0;

          for(int j=0;j<n;j++)
          {
              if(check>=even)
                break;
              if(i==j)
                continue;

                long long temp=__gcd(v[j],gcdd);
                if(temp!=1)
                {
                    check++;
                    gcdd=temp;

                }
          }

          if(check>=even)
          {
              maxxe=max(maxxe,gcdd);
          }
      }


      //cout<<maxxe<<endl;


      cout<<maxxo+maxxe<<endl;*/






    }
}