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;
struct edge {
  int v, next;
} e[100000 + 5 << 1];
bool book[1000000 + 5];
int n, cnt, tot, ans = 123456789, a[100000 + 5], h[1000000 + 5],
                 prime[1000000 + 5], dis[1000000 + 5], fa[1000000 + 5];
int read() {
  char c;
  int x = 0, f = 1;
  c = getchar();
  while (c > '9' || c < '0') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * f;
}
void add(int u, int v) { e[++tot].v = v, e[tot].next = h[u], h[u] = tot; }
bool Link(int x) {
  if (x == 1) {
    puts("1");
    return true;
  }
  if (!book[x]) {
    add(1, x), add(x, 1);
    return false;
  }
  int p = 0, q = 0, maxh = ceil(1.0 * sqrt(x)), s1 = 0, s2 = 0;
  for (int i = 2; i <= maxh; ++i)
    if (x % i == 0) {
      p = i;
      while (x % i == 0) x /= i, s1++;
      break;
    }
  for (int i = 2; i <= maxh; ++i)
    if (x % i == 0) {
      q = i;
      while (x % i == 0) x /= i, s2++;
      break;
    }
  if (x != 1) q = x, s2 = 1;
  if (!q) {
    if (s1 % 2 == 0) {
      puts("1");
      return true;
    } else
      add(1, p), add(p, 1);
    return false;
  } else {
    if (s1 % 2 == 0)
      add(1, q), add(q, 1);
    else if (s2 % 2 == 0)
      add(1, p), add(p, 1);
    else
      add(p, q), add(q, p);
    return false;
  }
  add(p, q), add(q, p);
  return false;
}
int main() {
  n = read();
  book[1] = 0;
  for (int i = 2; i <= 1000000 + 5 - 5; ++i) {
    if (!book[i]) prime[++cnt] = i;
    for (int j = 1; j <= cnt && i * prime[j] <= 1000000 + 5 - 5; j++) {
      book[i * prime[j]] = true;
      if (i % prime[j] == 0) break;
    }
  }
  for (int i = 1; i <= n; ++i) {
    a[i] = read();
    if (Link(a[i])) return 0;
  }
  int maxh = 1000;
  for (int i = 1; i <= maxh; ++i) {
    queue<int> q;
    q.push(i);
    memset(dis, 0x7f, sizeof(dis)), memset(fa, 0, sizeof(fa));
    dis[i] = 0;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int j = h[u]; j; j = e[j].next) {
        int v = e[j].v;
        if (dis[v] < 123456789) {
          if (v != fa[u]) ans = min(ans, dis[u] + dis[v] + 1);
        } else
          dis[v] = dis[u] + 1, q.push(v), fa[v] = u;
      }
    }
  }
  printf("%d", ans == 123456789 ? -1 : ans);
  return 0;
}