P1742D

// https://codeforces.com/contest/1742/problem/D
// P 1742 D

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,a,b) for (ll i=a; i<=b; i++)
#define ROF(i,a,b) for (ll i=a; i>=b; i--)
const ll nmax=1e5+7;
const ll N=1e9+7;
ll gcd_ll(ll a,ll b){
    return (b==0)?(a):(gcd_ll(b,a%b));
}
void solve()
{
    ll n;
    cin>>n;
    ll a[n+2];
    FOR(i,1,n) cin>>a[i];
    ll e=0;
    ROF(i,n,1){
        ll k=i;
        ROF(j,n,i){
            if (gcd_ll(a[k],a[j])==1){
                ll e=1;
                cout<<k+j<<"\n";
                return;
            }
        }
    }
    cout<<-1<<"\n";
}
int main()
{
    int t;
    for (cin>>t; t--; ){
        solve();
    }

}