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;
template <class T1, class T2>
ostream& operator<<(ostream& out, pair<T1, T2> p) {
  out << '(' << p.first << ',' << p.second << ')';
  return out;
}
template <class T1, class T2>
istream& operator>>(istream& in, pair<T1, T2>& p) {
  in >> p.first >> p.second;
  return in;
}
template <class T>
istream& operator>>(istream& in, vector<T>& v) {
  for (T& x : v) in >> x;
  return in;
}
template <class T>
ostream& operator<<(ostream& out, vector<vector<T>>& v) {
  for (vector<T>& x : v) out << x << '\n';
  return out;
}
template <class T>
ostream& operator<<(ostream& out, vector<T>& v) {
  for (T& x : v) out << x << ' ';
  return out;
}
long long gcd(long long a, long long b) {
  if (b > a) swap(a, b);
  return (b ? gcd(b, a % b) : a);
}
using ll = long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using tiii = pair<pair<int, int>, int>;
using vi = vector<int>;
using vl = vector<long long>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
const int h = 1000000007;
vvi pr(1000001);
vvi M(1000001);
vi level(1000001);
vi vis(1000001);
vi par(1000001);
int bfs(int x) {
  queue<int> q;
  vi explored{x};
  q.push(x);
  vis[x] = 1;
  par[x] = -1;
  while (!q.empty()) {
    int y = q.front();
    q.pop();
    for (int z : M[y]) {
      if (z == par[y]) continue;
      if (vis[z]) {
        int ans = level[y] + level[z] + 1;
        for (int d : explored) {
          vis[d] = 0;
          level[d] = 0;
        }
        return ans;
      }
      vis[z] = 1;
      explored.push_back(z);
      level[z] = level[y] + 1;
      q.push(z);
      par[z] = y;
    }
  }
  for (int d : explored) {
    vis[d] = 0;
    level[d] = 0;
  }
  return INT_MAX;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cerr.setstate(ios::failbit);
  int n;
  cin >> n;
  vl v(n);
  cin >> v;
  vl reduce(1000001);
  for (ll i = 1; i <= 1000; i++) {
    ll s = i * i;
    for (ll j = 1; s * j <= 1000000; j++) reduce[s * j] = j;
  }
  for (ll& x : v) x = reduce[x];
  for (ll x : v)
    if (x == 1) return cout << 1, 0;
  ;
  map<ll, int> m;
  for (ll x : v) m[x]++;
  for (auto p : m)
    if (p.second > 1) return cout << 2, 0;
  ;
  for (ll i = 2; i <= 1000000; i++) {
    if (pr[i].size() == 0)
      for (ll j = 2; i * j <= 1000000; j++) {
        pr[i * j].push_back(i);
      }
  }
  for (auto x : v) {
    if (pr[x].empty()) {
      M[1].push_back(x);
      M[x].push_back(1);
    } else {
      M[pr[x][0]].push_back(pr[x][1]);
      M[pr[x][1]].push_back(pr[x][0]);
    }
  }
  int ans = INT_MAX;
  for (int i = 1; i <= 1000; i++) ans = min(ans, bfs(i));
  cout << (ans == INT_MAX ? -1 : ans);
}