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("-O3")
using namespace std;
const int N = 1e6 + 5;
void pairsort(int a[], int b[], int n) {
  pair<int, int> pairt[n];
  for (int i = 0; i < n; i++) {
    pairt[i].first = a[i];
    pairt[i].second = b[i];
  }
  sort(pairt, pairt + n);
  for (int i = 0; i < n; i++) {
    a[i] = pairt[i].first;
    b[i] = pairt[i].second;
  }
}
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int isPrime(int n) {
  if (n < 2) return 0;
  if (n < 4) return 1;
  if (n % 2 == 0 or n % 3 == 0) return 0;
  for (int i = 5; i * i <= n; i += 6)
    if (n % i == 0 or n % (i + 2) == 0) return 0;
  return 1;
}
long long C(int n, int r) {
  if (r > n - r) r = n - r;
  long long ans = 1;
  for (int i = 1; i <= r; i++) {
    ans *= n - r + i;
    ans /= i;
  }
  return ans;
}
int mod = 1e9 + 7;
int modexpo(int x, int p) {
  int res = 1;
  x = x % mod;
  while (p) {
    if (p % 2) res = res * x;
    p >>= 1;
    x = x * x % mod;
    res %= mod;
  }
  return res;
}
int n, x, y, ans, mx, vis[N], h[N], p[N], root;
vector<int> v[N];
map<int, int> M;
map<pair<int, int>, int> mp;
vector<pair<int, int>> vc;
set<int> s;
void bfs(int x) {
  queue<int> q;
  vector<int> vc;
  q.push(x), h[x] = 0, vis[x] = 1, vc.push_back(x);
  while (q.size()) {
    x = q.front();
    q.pop();
    for (int i = 0; i < v[x].size(); i++) {
      if (!vis[v[x][i]])
        q.push(v[x][i]), h[v[x][i]] = h[x] + 1, vis[v[x][i]] = 1,
                         p[v[x][i]] = x, vc.push_back(v[x][i]);
      else if (v[x][i] != p[x])
        ans = (ans < h[x] + h[v[x][i]] + 1 ? ans : h[x] + h[v[x][i]] + 1);
    }
  }
  for (int i = 0; i < vc.size(); i++) vis[vc[i]] = h[vc[i]] = p[vc[i]] = 0;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n, s.insert(1);
  for (int i = 1; i <= n; i++) {
    cin >> x;
    vector<int> vv;
    for (int j = 2; j <= x / j; j++)
      if (x % j == 0) {
        int cnt = 0;
        while (x % j == 0) x /= j, cnt++;
        if (cnt % 2) vv.push_back(j);
      }
    if (x > 1) vv.push_back(x);
    if (!vv.size())
      return cout << 1, 0;
    else if (vv.size() == 1) {
      v[vv[0]].push_back(1), v[1].push_back(vv[0]);
      M[vv[0]]++, mx = (mx > vv[0] ? mx : vv[0]), s.insert(vv[0]);
      if (M[vv[0]] == 2) ans = 2;
    } else {
      vc.push_back({vv[0], vv[1]});
      mp[{vv[0], vv[1]}]++, mx = (mx > vv[0] ? mx : vv[0]),
                            mx = (mx > vv[1] ? mx : vv[1]), s.insert(vv[0]),
                            s.insert(vv[1]);
      if (mp[{vv[0], vv[1]}] == 2) ans = 2;
    }
  }
  if (ans) return cout << ans, 0;
  for (int i = 0; i < vc.size(); i++)
    if (M[vc[i].first] and M[vc[i].second]) return cout << 3, 0;
  ans = 1e9;
  for (int i = 0; i < vc.size(); i++) {
    x = vc[i].first, y = vc[i].second;
    v[x].push_back(y), v[y].push_back(x);
  }
  mx = sqrt(mx);
  while (s.size()) {
    x = *s.begin(), s.erase(s.begin());
    if (x > 2500) break;
    root = x, bfs(root);
  }
  if (ans == 1e9) ans = -1;
  cout << ans;
  return 0;
}