D - Coprime.cpp

#include <bits/stdc++.h>

using namespace std;

int gcd(int a, int b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

int t, n, a, idx[1005];
vector <pair<int, int> > v;

int main(){
    cin.tie(nullptr), ios::sync_with_stdio(false);
    cin >> t;
    for(int i = 1; i <= 1000; i++)
    for(int j = i; j <= 1000; j++){
        if(gcd(i, j) == 1) v.emplace_back(i, j);
    }
    while(t--){
        for(int i = 1; i <= 1000; i++) idx[i] = 0;
        cin >> n;
        for(int i = 1; i <= n; i++){
            cin >> a;
            idx[a] = max(idx[a], i);
        }

        int ans = -1;
        for(auto p : v){
            int n1 = idx[p.first], n2 = idx[p.second];
            if(n1 == 0 || n2 == 0) continue;
            ans = max(ans, n1 + n2);
        }

        cout << ans << "\n";
    }
}