#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
int n;
cin>>n;
vector<int> v(n);
map<int,int> mp;
for(int i=0;i<n;i++){
cin>>v[i];
mp[v[i]]=i;
}
int ans=-1;
for(int i=1;i<=1000;i++){
if(mp.find(i)==mp.end()){
continue;
}
for(int j=1;j<=1000;j++){
if(mp.find(j)!=mp.end()){
int x=__gcd(i,j);
if(x==1){
ans=max(ans,mp[i]+mp[j]+2);
}
}
}
}
cout<<ans<<endl;
}
signed main() {
// your code goes here
int t;
cin>>t;
while(t--)solve();
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgaW50IGxvbmcgbG9uZwp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdm9pZCBzb2x2ZSgpewoJaW50IG47CgljaW4+Pm47Cgl2ZWN0b3I8aW50PiB2KG4pOwoJbWFwPGludCxpbnQ+IG1wOwoJZm9yKGludCBpPTA7aTxuO2krKyl7CgkJY2luPj52W2ldOwoJCW1wW3ZbaV1dPWk7Cgl9CglpbnQgYW5zPS0xOwoJZm9yKGludCBpPTE7aTw9MTAwMDtpKyspewoJCQlpZihtcC5maW5kKGkpPT1tcC5lbmQoKSl7CgkJCQljb250aW51ZTsKCQkJfQoJCQlmb3IoaW50IGo9MTtqPD0xMDAwO2orKyl7CgkJCQlpZihtcC5maW5kKGopIT1tcC5lbmQoKSl7CgkJCQkJaW50IHg9X19nY2QoaSxqKTsKCQkJCQlpZih4PT0xKXsKCQkJCQkJYW5zPW1heChhbnMsbXBbaV0rbXBbal0rMik7CgkJCQkJfQoJCQkJfQoJCQl9CgkJCgl9CgkKCWNvdXQ8PGFuczw8ZW5kbDsKfQpzaWduZWQgbWFpbigpIHsKCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCWludCB0OwoJY2luPj50OwoJd2hpbGUodC0tKXNvbHZlKCk7CglyZXR1cm4gMDsKfQ==