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

NgozCjMgMiAxCjcKMSAzIDUgMiA0IDcgNwo1CjEgMiAzIDQgNQozCjIgMiA0CjYKNSA0IDMgMTUgMTIgMTYKNQoxIDIgMiAzIDYK

6
3
3 2 1
7
1 3 5 2 4 7 7
5
1 2 3 4 5
3
2 2 4
6
5 4 3 15 12 16
5
1 2 2 3 6