#include<bits/stdc++.h>
using namespace std;
int a[200009];
int n;
int idx[2000];
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=1000;i++) idx[i]=0;
for(int i=1;i<=n;i++){
idx[a[i]]=max(idx[a[i]],i);
}
int ans=-1;
for(int i=1;i<=1000;i++){
for(int j=1;j<=1000;j++){
if(__gcd(i,j)==1&&idx[i]>0&&idx[j]>0){
ans=max(ans,idx[i]+idx[j]);
}
}
}
cout<<ans<<endl;
}
int main(){
freopen("find.in","r",stdin);
freopen("find.out","w",stdout);
int tt=1;
cin>>tt;
while(tt--){
solve();
}
fclose(stdin);
fclose(stdout);
return 0;
}
