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;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
int dir[8][2] = {-1, 0, 1, 0, 0, -1, 0, 1, -1, -1, -1, 1, 1, -1, 1, 1};
template <typename S, typename T>
ostream &operator<<(ostream &os, const pair<S, T> x) {
  os << "(" << x.first << ", " << x.second << ")";
  return os;
}
template <typename S, typename T>
inline bool Min(S &a, const T &b) {
  return a > b ? a = b, true : false;
}
template <typename S, typename T>
inline bool Max(S &a, const T &b) {
  return a < b ? a = b, true : false;
}
template <typename S, typename T>
inline void Adm(S &a, const T &b) {
  a = (a + b) % MOD;
  if (a < 0) a += MOD;
}
template <typename T>
inline bool IsPri(T x) {
  if (x < 2) return false;
  for (T i = 2; i * i <= x; ++i)
    if (x % i == 0) return false;
  return true;
}
template <typename T>
inline T _Gcd(T a, T b) {
  while (b) {
    T t = b;
    b = a % b;
    a = t;
  }
  return a;
}
template <typename T>
inline int _BitCnt(T x) {
  int cnt = 0;
  while (x) ++cnt, x &= x - 1;
  return cnt;
}
inline long long Pow(long long a, long long n) {
  long long t = 1;
  a %= MOD;
  while (n > 0) {
    if (n & 1) t = t * a % MOD;
    a = a * a % MOD, n >>= 1;
  }
  return t % MOD;
}
inline int read() {
  static char buf[1000000], *p1 = buf, *p2 = buf;
  register int x = false;
  register char ch =
      p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)
          ? EOF
          : *p1++;
  ;
  register bool sgn = false;
  while (ch != '-' && (ch < '0' || ch > '9'))
    ch = p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)
             ? EOF
             : *p1++;
  ;
  if (ch == '-')
    sgn = true,
    ch = p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)
             ? EOF
             : *p1++;
  ;
  while (ch >= '0' && ch <= '9')
    x = (x << 1) + (x << 3) + (ch ^ 48),
    ch = p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)
             ? EOF
             : *p1++;
  ;
  return sgn ? -x : x;
}
const int N = 1e6 + 10;
pair<int, int> pri[N];
vector<pair<int, int> > e[N];
int dis[N];
bool vis[N];
bool odd(int x, int p) {
  int cnt = 0;
  while (x % p == 0) x /= p, ++cnt;
  return cnt & 1;
}
int main() {
  for (int i = 1; i < N; ++i) pri[i] = {1, 1};
  for (int i = 2; i < N; ++i) {
    if (pri[i].first == 1)
      for (int j = i; j < N; j += i)
        if (pri[j].first == 1)
          pri[j].first = i;
        else if (pri[j].second == 1)
          pri[j].second = i;
    if (pri[i].first != 1 && !odd(i, pri[i].first)) pri[i].first = 1;
    if (pri[i].second != 1 && !odd(i, pri[i].second)) pri[i].second = 1;
  }
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    e[pri[x].first].push_back({pri[x].second, i}),
        e[pri[x].second].push_back({pri[x].first, i});
  }
  int ans = INF;
  for (int st = 1; st * st < N; ++st)
    if (pri[st].second == 1) {
      queue<int> q;
      q.push(st);
      memset((vis), (0), sizeof(vis)), memset((dis), (0x3f), sizeof(dis)),
          dis[st] = 0;
      while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto it : e[u]) {
          int v = it.first, id = it.second;
          if (vis[id]) continue;
          vis[id] = 1;
          if (dis[v] == INF)
            dis[v] = dis[u] + 1, q.push(v);
          else
            Min(ans, dis[v] + dis[u] + 1);
        }
      }
    }
  printf("%d\n", ans == INF ? -1 : ans);
  return 0;
}