#include <bits/stdc++.h>
using namespace std;
const long long INF = 200000000 + 1;
const int N = 300006;
int a[N + 10], cnt[N + 10], cnt2[N + 10], val[N + 10], dp[N + 10], pr[N + 10],
    cnt1[N + 10], cnt3[N + 10];
vector<int> v[N + 10];
int gcd(int i, int j) {
  if (i % j == 0) return j;
  return gcd(j, i % j);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  for (int i = 2; i <= N; i++) {
    if (pr[i] != 0) continue;
    for (int j = i; j <= N; j += i) {
      if (pr[j] == 0) pr[j] = i;
    }
  }
  val[1] = 1;
  for (int i = 2; i <= N; i++) {
    for (int j = i; j <= N; j += i) {
      v[j].push_back(i);
    }
    int z = i;
    int w = 1;
    while (z != 1) {
      int prime = pr[z];
      while (z % prime == 0) {
        z = z / prime;
      }
      w = w * prime;
      cnt1[i]++;
    }
    val[i] = w;
  }
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    cnt[val[a[i]]]++;
  }
  if (cnt[1] > 0) {
    cout << 1 << '\n';
    return 0;
  }
  int g = a[1];
  int ans = n;
  for (int i = 2; i <= n; i++) g = gcd(g, a[i]);
  if (g != 1) {
    cout << "-1" << '\n';
    return 0;
  }
  for (int i = 2; i <= N; i++) {
    for (int j = i; j <= N; j += i) cnt3[i] += cnt[j];
  }
  for (int i = 2; i <= N; i++) {
    if (val[i] == i) {
      for (int j = 0; j < v[i].size(); j++) {
        if (cnt1[v[i][j]] % 2 == 0)
          cnt2[i] = cnt2[i] - cnt3[v[i][j]];
        else
          cnt2[i] = cnt2[i] + cnt3[v[i][j]];
      }
    }
  }
  dp[1] = 0;
  for (int i = 2; i <= N; i++) {
    int w = val[i];
    if (i != w) {
      if (cnt[i] > 0) ans = min(ans, dp[w] + 1);
      continue;
    }
    dp[i] = n;
    for (int j = 0; j < v[i].size(); j++) {
      if (cnt2[v[i][j]] != n) dp[i] = min(dp[i], dp[i / v[i][j]] + 1);
    }
    if (cnt[i] > 0) ans = min(ans, dp[i] + 1);
  }
  cout << ans << '\n';
}
