#include <bits/stdc++.h>   #pragma GCC optimize  -O3    using namespace std;   const int MAXN = 310000;   int n;   int a[MAXN];   vector<int> pr;   int bb[MAXN];   int go[MAXN];   int cc[MAXN];   int ans[MAXN];   vector<int> fc[MAXN];   int gcd(int a, int b) {     while (b) {       int q = a % b;       a = b;       b = q;     }     return a;   }   int dp[1 << 7];   int gg;   int gog[1 << 7];   void run(int x, int msk, int ml, int k) {     if (x == k) {       dp[msk] = cc[ml];       gog[msk] = ml;       return;     }     run(x + 1, msk, ml, k);     run(x + 1, msk + (1 << x), ml * fc[gg][x], k);   }   int main() {     ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);     for (int i = 0; i < MAXN; ++i) bb[i] = i;     for (int i = 2; i < MAXN; ++i) {       if (bb[i] == i) pr.push_back(i);       for (int j : pr) {         if (j * i >= MAXN || bb[i] < j) break;         bb[j * i] = j;       }     }     for (int i = 1; i < MAXN; ++i) {       int cur = 1;       int x = i;       while (x != 1) {         int d = bb[x];         while (x % d == 0) x /= d;         cur *= d;         fc[i].push_back(d);       }       go[i] = cur;     }     cin >> n;     int now = 0;     fill(ans, ans + MAXN, 1000);     for (int i = 0; i < n; ++i) {       cin >> a[i];       now = gcd(now, a[i]);       a[i] = go[a[i]];       ++cc[a[i]];       ans[a[i]] = 1;     }     if (now != 1) {       cout << -1 <<   n ;       return 0;     }     for (int i = 1; i < MAXN; ++i) {       for (int j = 2 * i; j < MAXN; j += i) cc[i] += cc[j];     }     for (int i = MAXN - 1; i > 1; --i) {       if (go[i] != i) continue;       int k = fc[i].size();       gg = i;       run(0, 0, 1, k);       for (int i = (1 << k) - 1; i > 0; --i) {         for (int j = (i - 1) & i; j > 0; j = (j - 1) & i) dp[j] -= dp[i];         dp[0] -= dp[i];       }       for (int j = 0; j < (1 << k); ++j)         if (dp[j]) ans[gog[j]] = min(ans[gog[j]], ans[i] + 1);     }     cout << ans[1] <<   n ;     return 0;   }   