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;
const int inf = 0x3f3f3f3f;
int p[2000100], pn, pos[2000100], ans, R, n, dis[2000100];
bool ntp[2000100];
inline int read() {
  int s = 0, w = 1;
  char ch = getchar();
  while (ch < 48 || ch > 57) {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= 48 && ch <= 57)
    s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
  return s * w;
}
void init(int n) {
  ntp[1] = true;
  pos[1] = R = 1;
  for (register int i = 2; i <= n; i++) {
    if (!ntp[i]) {
      p[++pn] = i, pos[i] = pn + 1;
      if (i < 1000) ++R;
    }
    for (int j = 1; j <= pn && p[j] * i <= n; ++j) {
      ntp[p[j] * i] = true;
      if (i % p[j] == 0) break;
    }
  }
}
int cnt, head[2000100];
struct Edge {
  int to, nxt;
} edge[2000100 << 1];
void add(int a, int b) {
  ++cnt;
  edge[cnt].to = b;
  edge[cnt].nxt = head[a];
  head[a] = cnt;
}
void check(int x) {
  int p = 0, q = 0;
  for (register int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      int cnt = 0;
      while (x % i == 0) ++cnt, x /= i;
      if (cnt & 1) {
        if (!p)
          p = i;
        else
          q = i;
      }
    }
  }
  if (x > 1) {
    if (!p)
      p = x;
    else
      q = x;
  }
  if (!p && !q) {
    printf("1\n");
    exit(0);
  }
  if (!q) {
    add(pos[p], 1), add(1, pos[p]);
  } else {
    add(pos[q], pos[p]), add(pos[p], pos[q]);
  }
}
int main() {
  cin >> n;
  init(1000000);
  ans = inf;
  for (int i = 1; i <= n; i++) {
    int x = read();
    check(x);
  }
  for (int s = 1; s <= R; ++s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    queue<pair<int, int> > q;
    q.push(make_pair(s, 0));
    while (!q.empty()) {
      int u = q.front().first, fa = q.front().second;
      q.pop();
      for (int i = head[u]; i; i = edge[i].nxt) {
        int v = edge[i].to;
        if (v == fa) continue;
        if (dis[v] >= inf) {
          dis[v] = dis[u] + 1;
          q.push(make_pair(v, u));
        } else if (dis[u] + dis[v] > 0) {
          ans = min(ans, dis[u] + dis[v] + 1);
        }
      }
    }
  }
  if (ans > n) {
    printf("-1\n");
  } else {
    printf("%d\n", ans);
  }
  return 0;
}