///*******************************THINK TWICE CODE ONCE*******************************///
///*******************************NO CODE NO FOOD*******************************///
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define loop(n) for(int i=0;i<n;i++)
#define ll long long
using namespace std;
//int f[1001];
//vector<int>a[100001];
int dis[100001];
//int ans(int )
int main()
{
    //freopen("team.in", "r", stdin);
    //freopen("output.txt","w",stdout);
    fast;
    int t;
    cin>>t;
    while(t--)
    {

 int n;
 cin>>n;
 int a[n];
 int f[1001]={0};
 map<int,int>m;
 loop(n)
 {
     cin>>a[i];
     m[a[i]]=i;
     f[a[i]]=1;
 }

 int mx=0;
 loop(1001)
 {
     for(int j=0;j<1001;j++)
     {
         if(f[i]==1&&f[j]==1)
         {

            int c= __gcd(i,j);
            if(c==1)
            {
//cout<<"a ";
          mx=max(mx,(m[i]+m[j]));
            }

         }
     }
 }
 if(mx==0)
    cout<<-1<<endl;
 else
 cout<<mx+2<<endl;
    }
    return 0;
}