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;
namespace yspm {
inline long long read() {
  long long res = 0, f = 1;
  char k;
  while (!isdigit(k = getchar()))
    if (k == '-') f = -1;
  while (isdigit(k)) res = res * 10 + k - '0', k = getchar();
  return res * f;
}
const long long N = 2e6 + 10, inf = 0x3f3f3f3f3f3f3f3f;
long long num, pri[N], ans, pos[N], dis[N], n, R;
bool fl[N];
inline void prework() {
  fl[1] = 1;
  pos[1] = R = 1;
  for (long long i = 2; i < N; ++i) {
    if (!fl[i]) {
      pri[++num] = i;
      pos[i] = num + 1;
      if (i < 1000) ++R;
    }
    for (long long j = 1; j <= num && i * pri[j] < N; ++j) {
      fl[pri[j] * i] = 1;
      if (i % pri[j] == 0) break;
    }
  }
  return;
}
long long cnt, head[N];
struct node {
  long long to, nxt;
} e[N << 1];
inline void add(long long u, long long v) {
  e[++cnt].nxt = head[u];
  e[cnt].to = v;
  return head[u] = cnt, void();
}
inline void build(long long x) {
  long long tot = 0, a[10] = {0};
  for (long long i = 2; i * i <= x; ++i) {
    if (x % i == 0) {
      long long cnt = 0;
      while (x % i == 0) ++cnt, x /= i;
      if (cnt & 1) a[++tot] = i;
    }
  }
  if (x > 1) a[++tot] = x;
  if (!a[1] && !a[2]) puts("1"), exit(0);
  if (!a[2])
    add(pos[a[1]], 1), add(1, pos[a[1]]);
  else
    add(pos[a[1]], pos[a[2]]), add(pos[a[2]], pos[a[1]]);
}
signed main() {
  prework();
  n = read();
  ans = inf;
  for (long long i = 1; i <= n; ++i) build(read());
  for (long long s = 1; s <= R; ++s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    queue<pair<long long, long long> > q;
    q.push(make_pair(s, 0));
    while (!q.empty()) {
      long long fr = q.front().first, fa = q.front().second;
      q.pop();
      for (long long i = head[fr]; i; i = e[i].nxt) {
        long long t = e[i].to;
        if (t == fa) continue;
        if (dis[t] >= inf)
          dis[t] = dis[fr] + 1, q.push(make_pair(t, fr));
        else if (dis[fr] + dis[t] > 0)
          ans = min(ans, dis[t] + dis[fr] + 1);
      }
    }
  }
  if (ans > n) ans = -1;
  printf("%lld\n", ans);
  return 0;
}
}  // namespace yspm
signed main() { return yspm::main(); }