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


        long long p=0;




        for(int i=1;i<=104;i++)
        {
            for(int j=1;j<=104;j++)
            {
                map<long long,long long>mapp;
                long long cnt1=0;
                for(int k=0;k<n;k++)
                {
                    if(v[k]%i==0)
                        cnt1++;

                }

                if(cnt1>=odd)
                {
                    long long y1=0;
                    for(int k=0;k<n;k++)
                    {
                        if(y1>=odd)
                            break;
                        if(v[k]%i==0&&v[k]%j!=0)
                        {
                            y1++;
                            mapp[k]++;

                        }
                    }

                    for(int k=0;k<n;k++)
                    {
                        if(y1>=odd)
                            break;
                        if(v[k]%i==0)
                        {
                            y1++;
                            mapp[k]++;

                        }
                    }
                }

                long long cnt2=0;

                for(int k=0;k<n;k++)
                {
                    if(mapp[k]==0&&v[k]%j==0)
                        cnt2++;
                }


                if(cnt2>=even&&cnt1>=odd)
                {
                    long long bye=i+j;
                    //cout<<i<<" "<<j<<endl;

                    p=max(bye,p);

                }


            }
        }

        cout<<p<<endl;


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


            }

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

                long long u1=0;

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

                }

            }

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

       // cout<<anse<<" "<<anso<<endl;

        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;*/






    }
}