Problem: You are given an array a of length n that has a special condition: every element in this array has at most 7 divisors. Find the length of the shortest non-empty subsequence of this array product of whose elements is a perfect square.

A sequence a is a subsequence of an array b if a can be obtained from b by deletion of several (possibly, zero or all) elements.

Input

The first line contains an integer n (1 ≤ n ≤ 10^5) — the length of a.

The second line contains n integers a_1, a_2, …, a_{n} (1 ≤ a_i ≤ 10^6) — the elements of the array a.

Output

Output the length of the shortest non-empty subsequence of a product of whose elements is a perfect square. If there are several shortest subsequences, you can find any of them. If there's no such subsequence, print "-1".

Examples

Input


3
1 4 6


Output


1

Input


4
2 3 6 6


Output


2

Input


3
6 15 10


Output


3

Input


4
2 3 5 7


Output


-1

Note

In the first sample, you can choose a subsequence [1].

In the second sample, you can choose a subsequence [6, 6].

In the third sample, you can choose a subsequence [6, 15, 10].

In the fourth sample, there is no such subsequence.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
void maxtt(T& t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T& t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
string direc = "RDLU";
const long long MOD2 = (long long)1000000007 * (long long)1000000007;
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int& x, int y, int mod = 1000000007) {
  x += y;
  if (x >= mod) x -= mod;
  if (x < 0) x += mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 1000000007) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
int a[1000035], p[1000035];
vector<int> mp[1000035];
int zid[1000035], zz = 1000;
void init() {
  for (int i = 2; i < 1000035; i++)
    if (!p[i]) {
      for (int j = i; j < 1000035; j += i) {
        p[j] = i;
      }
    }
}
int gid(int x) {
  if (x <= 1000) return x;
  if (zid[x] == 0) zid[x] = ++zz;
  return zid[x];
}
void cal() {
  set<int> S;
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    map<int, int> mpt;
    for (int j = a[i]; j > 1; j /= p[j]) {
      mpt[p[j]]++;
    }
    vector<int> vp;
    for (auto& p : mpt)
      if (p.second & 1) vp.push_back(p.first);
    assert(vp.size() == 1 || vp.size() == 2);
    int z = vp[0];
    int y = vp.size() == 1 ? 1 : vp[1];
    if (S.count(y * z)) {
      puts("2");
      exit(0);
    }
    S.insert(y * z);
    y = gid(y);
    z = gid(z);
    mp[z].push_back(y);
    mp[y].push_back(z);
  }
}
int dis[1000035], L = (1 << 30);
void fmain(int tid) {
  init();
  scanf("%d", &n);
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    scanf("%d", a + i);
    k = a[i];
    int z = sqrt(k);
    if (z * z == k) {
      puts("1");
      return;
    }
  }
  sort(a + 1, a + 1 + n);
  for (int(i) = 1; (i) <= (int)(n - 1); (i)++)
    if (a[i] == a[i + 1]) {
      puts("2");
      return;
    }
  cal();
  for (int(i) = 1; (i) <= (int)(min(1000, zz)); (i)++) {
    for (int(j) = 1; (j) <= (int)(zz); (j)++) {
      dis[j] = (1000000000);
    }
    dis[i] = 0;
    queue<pair<int, int> > q;
    q.push(make_pair(i, 0));
    while (!q.empty()) {
      int u = q.front().first, fa = q.front().second;
      q.pop();
      for (int v : mp[u]) {
        if (v == fa) continue;
        if (dis[v] >= (1000000000)) {
          dis[v] = dis[u] + 1;
          q.push(make_pair(v, u));
        } else if (dis[u] + dis[v] > 0) {
          mintt(L, dis[u] + dis[v] + 1);
        }
      }
    }
  }
  if (L == (1 << 30)) et();
  printf("%d\n", L);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}