#include <bits/stdc++.h>
using namespace std;
const int Np = 2000;
int prime[Np + 5], cntp;
bool notp[Np + 5] = {true, true};
void find_prime(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!notp[i]) prime[++cntp] = i;
    for (int j = 1; j <= cntp && i * prime[j] <= n; ++j) {
      notp[i * prime[j]] = true;
      if (!(i % prime[j])) break;
    }
  }
}
const int N = 1000000;
vector<int> G[N + 5];
int ans, dep[N + 5];
bool vis[N + 5];
void bfs(int u, int fa) {
  queue<pair<int, int>> Q;
  Q.push({u, fa});
  vis[u] = true;
  dep[u] = dep[fa] + 1;
  while (!Q.empty()) {
    u = Q.front().first;
    fa = Q.front().second;
    Q.pop();
    for (int v : G[u])
      if (v != fa) {
        if (!vis[v]) {
          Q.push({v, u});
          vis[v] = true;
          dep[v] = dep[u] + 1;
        } else
          ans = min(ans, dep[u] + dep[v] - 1);
      }
  }
}
int main() {
  find_prime(Np);
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    int u = 1, v = 1, lmt = sqrt(x + 0.5);
    for (int j = 1; prime[j] <= lmt; ++j) {
      if (x % prime[j] == 0) {
        int cnt = 0;
        while (x % prime[j] == 0) {
          x /= prime[j];
          ++cnt;
        }
        if (cnt & 1) {
          if (u == 1)
            u = prime[j];
          else
            v = prime[j];
        }
      }
    }
    if (x != 1) {
      if (u == 1)
        u = x;
      else
        v = x;
    }
    G[u].push_back(v);
    G[v].push_back(u);
  }
  ans = INT_MAX;
  for (int i = 1; i <= 1000; ++i) {
    if (!G[i].empty()) {
      memset(vis, false, sizeof(vis));
      bfs(i, 0);
    }
  }
  if (ans == INT_MAX) ans = -1;
  printf("%d\n", ans);
  return 0;
}
