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 long long INF = 4e18;
const long long mod2 = 1e9 + 7;
const long long mod = 998244353;
long long power(long long a, long long b, long long mod) {
  long long prod = 1;
  long long mult = a;
  while (b != 0) {
    if (b % 2) {
      prod *= mult;
      prod %= mod;
    }
    mult *= mult;
    mult %= mod;
    b /= 2;
  }
  return prod;
}
long long mod_inv(long long q, long long mod) { return power(q, mod - 2, mod); }
const long long MAXN = 1e6 + 10;
;
vector<long long> normalize[MAXN];
long long isPrime[MAXN];
vector<pair<long long, long long> > adj[MAXN];
long long visited[MAXN];
long long glbl = INF;
set<long long> marked;
struct info {
  long long root, edge, source, depth;
};
vector<long long> used;
long long depths[MAXN];
void bfs(long long root, long long edge, long long source, long long depth) {
  used.clear();
  queue<info> q;
  q.push({root, edge, source, depth});
  visited[root] = true;
  used.push_back(root);
  depths[root] = 1;
  while (!q.empty()) {
    long long root, edge, source, depth;
    auto l = q.front();
    q.pop();
    root = l.root;
    edge = l.edge;
    source = l.source;
    depth = l.depth;
    for (auto i : adj[root]) {
      if (!visited[i.first]) {
        q.push({i.first, i.second, source, depth + 1});
        visited[i.first] = true;
        used.push_back(i.first);
        depths[i.first] = depth + 1;
      } else if (i.second != edge) {
        glbl = min(glbl, depth + depths[i.first] - 1);
      }
    }
  }
  for (auto i : used) {
    visited[i] = false;
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  for (long long i = 2; i < MAXN; i++) isPrime[i] = 1;
  for (long long i = 2; i < MAXN; i++) {
    if (isPrime[i] == 1) {
      for (long long j = i; j < MAXN; j += i) {
        isPrime[j] = i;
      }
    }
    normalize[i] = normalize[i / isPrime[i]];
    if (find(normalize[i].begin(), normalize[i].end(), isPrime[i]) ==
        normalize[i].end()) {
      normalize[i].push_back(isPrime[i]);
    } else {
      normalize[i].erase(
          find(normalize[i].begin(), normalize[i].end(), isPrime[i]));
    }
  }
  long long n;
  cin >> n;
  vector<long long> a(n);
  long long cnt = 0;
  for (auto& i : a) {
    cnt++;
    cin >> i;
    auto l = normalize[i];
    if (l.size() == 0) l.push_back(1);
    if (l.size() == 1) l.push_back(1);
    adj[l[0]].push_back({l[1], cnt});
    adj[l[1]].push_back({l[0], cnt});
  }
  long long mn = INF;
  for (long long i = 0; i * i < MAXN; i++) {
    glbl = INF;
    bfs(i, -1, i, 1);
    mn = min(mn, glbl);
  }
  if (mn == INF) mn = -1;
  cout << mn << '\n';
}