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>
#pragma GCC optimize(2)
using namespace std;
inline int read() {
  char c = getchar();
  int x = 0;
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  if (f) x = -x;
  return x;
}
int n, m, res;
struct edge {
  int to, nxt;
} e[1000005 << 1];
int tot, head[1000005];
inline void adde(int u, int v) {
  e[++tot] = (edge){v, head[u]};
  head[u] = tot;
}
int pri[1000005], mp[1000005], cnt, t1000;
bool vis[1000005];
void prework(int n) {
  vis[1] = 1;
  for (register int i = (2); i <= (n); ++i) {
    if (!vis[i]) {
      pri[++cnt] = i, mp[i] = cnt + 1;
      if (i < 1000) t1000++;
    }
    for (register int j = (1); j <= (cnt); ++j) {
      if (i * pri[j] > n) break;
      vis[i * pri[j]] = 1;
      if (i % pri[j])
        ;
      else
        break;
    }
  }
}
void ins(int x) {
  int a = 0, b = 0;
  for (register int i = (2); i <= (x / i); ++i) {
    if (x % i) continue;
    int cnt = 0;
    do cnt ^= 1, x /= i;
    while (x % i == 0);
    if (cnt) {
      if (a)
        b = i;
      else
        a = i;
    }
  }
  if (x > 1) {
    if (a)
      b = x;
    else
      a = x;
  }
  if (!a && !b) {
    cout << 1;
    exit(0);
  }
  if (!b)
    adde(1, mp[a]), adde(mp[a], 1);
  else
    adde(mp[a], mp[b]), adde(mp[b], mp[a]);
}
struct node {
  int u, fa;
};
int dis[1000005];
void bfs(int s) {
  memset(dis, 63, sizeof dis);
  dis[s] = 0;
  queue<node> q;
  q.push((node){s, 0});
  while (!q.empty()) {
    int u = q.front().u, fa = q.front().fa;
    q.pop();
    for (int i = head[u]; i; i = e[i].nxt) {
      int v = e[i].to;
      if (v == fa) continue;
      if (dis[v] == 0x3f3f3f3f)
        dis[v] = dis[u] + 1, q.push((node){v, u});
      else
        res = min(res, dis[u] + dis[v] + 1);
    }
  }
}
int main() {
  n = read(), res = 0x3f3f3f3f;
  prework(1000000);
  for (register int i = (1); i <= (n); ++i) ins(read());
  for (register int i = (1); i <= (t1000); ++i) bfs(i);
  if (res == 0x3f3f3f3f) res = -1;
  cout << res;
  return 0;
}