#include <bits/stdc++.h>
using namespace std;
const long long maxn = 3e5 + 7;
const long long maxm = (1 << 8) + 7;
const long long mod = 1e9 + 7;
const long long INF = 1e9 + 7;
const long long mlog = 20;
const long long SQ = 400;
vector<long long> taj[maxn];
vector<long long> divs[maxn];
long long mark[maxn];
long long dp[maxm], ctr[maxm];
long long a[maxn];
long long cnt[maxn];
inline void prep() {
  for (long long i = 1; i < maxn; i++) {
    if (!mark[i] && i != 1)
      for (long long j = i; j < maxn; j += i)
        if (!mark[j]) mark[j] = i;
    for (long long j = i; j < maxn; j += i) divs[j].push_back(i);
  }
  for (long long i = 1; i < maxn; i++) {
    long long base = mark[i], tmp = i;
    while (tmp != 1) {
      while (mark[tmp] == base) tmp /= base;
      taj[i].push_back(base), base = mark[tmp];
    }
  }
}
int32_t main() {
  ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
  ;
  prep();
  long long n;
  cin >> n;
  for (long long i = 0; i < n; i++) cin >> a[i];
  for (long long i = 0; i < n; i++)
    for (long long v : divs[a[i]]) cnt[v]++;
  long long ans = +INF;
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < maxm; j++) ctr[j] = 0, dp[j] = +INF;
    long long k = taj[a[i]].size();
    long long MASK = (1 << k) - 1;
    for (long long mask = 0; mask < (1 << k); mask++) {
      long long base = 1;
      for (long long bit = 0; bit < k; bit++)
        if (mask & (1 << bit)) base *= taj[a[i]][bit];
      ctr[mask] = cnt[base] - 1;
    }
    for (long long mask = MASK; mask > 0; mask--) {
      for (long long nmask = (mask - 1) & mask;; nmask = (nmask - 1) & mask) {
        ctr[nmask] -= ctr[mask];
        if (nmask == 0) break;
      }
    }
    for (long long mask = 0; mask < (1 << k); mask++)
      if (ctr[mask] > 0) dp[MASK ^ mask] = 1;
    for (long long mask = 0; mask < (1 << k); mask++) {
      if (dp[mask] != 1) continue;
      for (long long nmask = mask;; nmask = (nmask - 1) & mask) {
        dp[nmask] = 1;
        if (nmask == 0) break;
      }
    }
    dp[0] = 0;
    for (long long mask = 1; mask < (1 << k); mask++) {
      if (dp[mask] == 1) continue;
      for (long long nmask = mask;; nmask = (nmask - 1) & mask) {
        if (dp[nmask] == 1) dp[mask] = min(dp[mask], dp[mask - nmask] + 1);
        if (nmask == 0) break;
      }
    }
    ans = min(ans, dp[MASK] + 1);
  }
  cout << (ans == +INF ? -1 : ans) << "\n";
  return 0;
}
