#include<iostream>
using namespace std;
int a[1000005],n;
int f(int n,int m){
if(!m) return n;
return f(m,n%m);
}
void nec_loc_shut(){
int m=-1;
for(int i=n;i>0;i--){
for(int j=i;j>0;j--){
if(f(a[i],a[j])==1){
m = max(m,i+j);
break;
}
}
}
cout<<m<<endl;
}
int main(){
int time;
cin>>time;
while(time--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
nec_loc_shut();
}
return 0;
}
