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", "unroll-loops")
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
istream &operator>>(istream &o, vector<int> &arr) {
  for (int i = 0; i < arr.size(); i++) o >> arr[i];
  return o;
}
inline long long int gcd(long long int a, long long int b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
inline long long int lcm(long long int a, long long int b) {
  return a / gcd(a, b) * b;
}
inline long long int gcdex(long long int a, long long int b, long long int &x,
                           long long int &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long int xx, yy;
  long long int gc = gcdex(b, a % b, yy, xx);
  x = xx;
  y = yy - (a / b) * xx;
  return gc;
}
inline long long int pwm(long long int xx, long long int pow,
                         long long int MD) {
  if (pow < 0) {
    pow = pow % (MD - 1) + MD - 1;
  }
  long long int mlt = 1;
  while (pow) {
    if (pow & 1) {
      mlt *= xx;
      mlt %= MD;
    }
    xx *= xx;
    pow >>= 1;
    xx %= MD;
  }
  return mlt;
}
inline int inv(long long int r, int _mod) {
  return pwm(r % _mod, _mod - 2, _mod);
}
inline int64_t hilbertOrder(int x, int y, int pow, int rotate) {
  if (pow == 0) {
    return 0;
  }
  int hpow = 1 << (pow - 1);
  int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);
  seg = (seg + rotate) & 3;
  const int rotateDelta[4] = {3, 0, 0, 1};
  int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
  int nrot = (rotate + rotateDelta[seg]) & 3;
  int64_t subSquareSize = int64_t(1) << (2 * pow - 2);
  int64_t ans = seg * subSquareSize;
  int64_t add = hilbertOrder(nx, ny, pow - 1, nrot);
  ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
  return ans;
}
vector<int> arr;
vector<vector<int>> vert(1e6, vector<int>(0));
int inf = 1e9;
vector<bool> was(1e6, false);
vector<int> alll;
vector<int> mapik(1e6, -1);
vector<int> parent(1e6, -1);
deque<int> q;
int bfs(int v) {
  mapik.clear();
  parent.clear();
  q.clear();
  mapik[v] = 0;
  parent[v] = -1;
  q.push_back(v);
  was[v] = true;
  int ans = inf;
  while (!q.empty()) {
    int now = q.front();
    q.pop_front();
    for (int son : vert[now]) {
      if (!was[son]) {
        q.push_back(son);
        mapik[son] = mapik[now] + 1;
        parent[son] = now;
        was[son] = true;
      } else if (parent[now] != son) {
        ans = min(ans, mapik[son] + mapik[now] + 1);
      }
    }
  }
  for (int son : alll) was[son] = false;
  for (int son : alll) mapik[son] = inf;
  for (int son : alll) parent[son] = -1;
  return ans;
}
set<pair<int, int>> allpairs;
void solve() {
  int n;
  cin >> n;
  arr.resize(n);
  cin >> arr;
  int lol = -1;
  for (int i = 0; i < n; i++) {
    int h = arr[i];
    vector<int> kek;
    for (int j = 2; j * j <= h; j++) {
      if (h % j == 0) {
        int deg = 0;
        while (h % j == 0) {
          deg++;
          h /= j;
        }
        if (deg % 2 == 1) {
          kek.push_back(j);
        }
      }
    }
    if (h != 1) kek.push_back(h);
    if (kek.size() == 0) {
      cout << 1 << endl;
      return;
    }
    if (kek.size() == 1) {
      kek.push_back(1);
    }
    vert[kek[0]].push_back(kek[1]);
    vert[kek[1]].push_back(kek[0]);
    if (allpairs.find({min(kek[0], kek[1]), max(kek[0], kek[1])}) !=
        allpairs.end()) {
      lol = 2;
      allpairs.insert({min(kek[0], kek[1]), max(kek[0], kek[1])});
    }
    alll.push_back(kek[0]);
    alll.push_back(kek[1]);
  }
  if (lol != -1) {
    cout << lol << endl;
    return;
  }
  sort(alll.begin(), alll.end());
  alll.erase(unique(alll.begin(), alll.end()), alll.end());
  int ans = inf;
  for (int i = 1; i < 1e3 + 2; i++) {
    if (vert[i].size() == 0) continue;
    int res = bfs(i);
    ans = min(res, ans);
  }
  if (ans == inf)
    cout << -1;
  else
    cout << ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  unsigned int beg_time = clock();
  int n = 1;
  for (int i = 0; i < n; i++) solve();
  unsigned int end_time = clock();
  return 0;
}