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 maxa = 1000005;
vector<long long> g[maxa];
bool used[maxa];
long long le[maxa];
long long ans = 1e18;
vector<long long> h;
long long is[maxa];
long long pr[maxa];
void bfs(long long x) {
  deque<long long> q;
  q.push_back(x);
  for (long long i = 0; i < h.size(); ++i) {
    if (h[i] == x) {
      is[h[i]] = 0;
    } else {
      is[h[i]] = 1e18;
    }
  }
  used[x] = true;
  pr[x] = (-1);
  while (!q.empty()) {
    deque<long long> q1;
    while (!q.empty()) {
      long long z = q.front();
      q.pop_front();
      for (long long i = 0; i < g[z].size(); ++i) {
        long long v = g[z][i];
        if (used[v] && v != pr[z]) {
          ans = min(ans, is[z] + is[v] + 1);
        } else if (!used[v]) {
          used[v] = true;
          q1.push_back(v);
          pr[v] = z;
          is[v] = is[z] + 1;
        }
      }
    }
    q = q1;
  }
  for (long long i = 0; i < h.size(); ++i) {
    used[h[i]] = false;
  }
}
vector<long long> rasl(long long x) {
  vector<long long> v;
  if (x == 1) {
    return v;
  }
  for (long long i = 2; i * i <= x; ++i) {
    if (x % i == 0) {
      v = rasl(x / i);
      v.push_back(i);
      return v;
    }
  }
  v.push_back(x);
  return v;
}
vector<long long> go(vector<long long> v) {
  sort(v.begin(), v.end());
  long long t = 0;
  while (t < (long long)v.size() - 1) {
    if (v[t] == v[t + 1]) {
      v.erase(v.begin() + t);
      v.erase(v.begin() + t);
    } else {
      ++t;
    }
  }
  return v;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  long long a[n];
  vector<long long> b[n];
  set<vector<long long> > d;
  for (long long i = 0; i < n; ++i) {
    long long x;
    cin >> x;
    b[i] = go(rasl(x));
    if (d.count(b[i])) {
      ans = min(ans, 2LL);
    } else {
      d.insert(b[i]);
    }
    if (b[i].empty()) {
      cout << 1 << endl;
      return 0;
    } else if (b[i].size() == 1) {
      b[i].push_back(1000001);
    }
  }
  vector<pair<long long, long long> > z(n);
  for (long long i = 0; i < n; ++i) {
    z[i] = {b[i][0], b[i][1]};
    g[z[i].first].push_back(z[i].second);
    g[z[i].second].push_back(z[i].first);
  }
  for (long long i = 0; i < maxa; ++i) {
    if (g[i].size()) {
      h.push_back(i);
    }
  }
  for (long long i = 2; i < 1005; ++i) {
    if (rasl(i).size() == 1) bfs(i);
  }
  bfs(1000001);
  if (ans == 1e18) {
    cout << (-1);
    return 0;
  }
  cout << ans << endl;
  return 0;
}