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 maxn = 1e6 + 10;
const int maxm = 2e5 + 10;
const int mod = 1e9 + 7;
const long long linf = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
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 S, typename T>
inline void Mum(S &a, const T &b) {
  a = 1LL * a * b % mod;
}
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;
}
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;
}
inline long long qpow(long long a, long long n) {
  long long t = 1;
  while (n) {
    if (n & 1) t = t * a % mod;
    a = a * a % mod, n >>= 1;
  }
  return t % mod;
}
void p_bit(long long x) { cout << bitset<32>(x) << ':' << x << endl; }
vector<int> e[maxn];
int ans = inf;
void add(int x, int y) { e[x].push_back(y); }
void cal(int x) {
  vector<int> s;
  for (long long i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      int cnt = 0;
      while (x % i == 0) ++cnt, x /= i;
      cnt %= 2;
      if (cnt & 1) s.push_back(i);
    }
  }
  if (x != 1) s.push_back(x);
  if (s.size() == 0)
    ans = 1;
  else if (s.size() == 1)
    add(1, s[0]), add(s[0], 1);
  else
    add(s[0], s[1]), add(s[1], s[0]);
}
int d[maxn], vis[maxn], idx;
int pre[maxn];
int bfs(int x) {
  queue<int> q;
  q.push(x);
  vis[x] = idx;
  pre[x] = -1;
  d[x] = 0;
  int ans = inf;
  while (!q.empty()) {
    x = q.front();
    q.pop();
    for (auto v : e[x]) {
      if (v == pre[x]) continue;
      if (vis[v] != idx)
        q.push(v), d[v] = d[x] + 1, vis[v] = idx, pre[v] = x;
      else
        ans = min(ans, d[v] + d[x] + 1);
    }
  }
  return ans;
}
int a[maxn], b[maxn];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    cal(a[i]);
  }
  if (ans == 1) cout << ans << endl, exit(0);
  int res = inf;
  for (int i = 1; i <= 1000; i++) {
    ++idx;
    if (e[i].size() == 0) continue;
    res = min(res, bfs(i));
  }
  if (res == inf)
    cout << -1 << endl;
  else
    cout << res << endl;
  return 0;
}