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 int mxn = 1e5 + 5, zxcv = 1e6 + 2;
vector<int> adj[zxcv], primes;
int par[zxcv], dis[zxcv];
bool been[zxcv], pos[zxcv];
stack<int> me, you;
int n, ans = 1e7;
pair<int, int> done(int);
void bfs(int);
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  primes.push_back(2);
  for (int i = 3; i < 1e3; i += 2) {
    bool a = true;
    for (auto q : primes)
      if (i % q == 0) {
        a = 0;
        break;
      }
    if (a) primes.push_back(i);
  }
  cin >> n;
  int a[n];
  pair<int, int> mee;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) {
    int w = sqrt(a[i]);
    if ((w * w) == a[i] || (w + 1) * (w + 1) == a[i]) {
      cout << 1;
      return 0;
    }
  }
  for (int i = 0; i < n; i++) {
    mee = done(a[i]);
    adj[mee.first].push_back(mee.second);
    adj[mee.second].push_back(mee.first);
    if (pos[mee.first * mee.second]) {
      cout << 2;
      return 0;
    } else
      pos[mee.first * mee.second] = 1;
  }
  for (auto q : primes) {
    bfs(q);
    memset(been, 0, sizeof been);
    memset(par, -1, sizeof par);
    memset(dis, 0, sizeof dis);
  }
  bfs(1);
  if (ans > 1e5)
    cout << -1;
  else
    cout << ans;
  return 0;
}
pair<int, int> done(int x) {
  pair<int, int> out = make_pair(1, 1);
  while (x % 4 == 0) x /= 4;
  if (x % 2 == 0) {
    out.first = 2;
    x /= 2;
  }
  for (int i = 3; i <= sqrt(x); i += 2) {
    while (x % (i * i) == 0) x /= (i * i);
    if (x % i == 0) {
      x /= i;
      if (x == 1) {
        out.second = i;
        return out;
      } else
        out.first = i;
    }
  }
  if (x != 1) out.second = x;
  return out;
}
void bfs(int u) {
  me.push(u);
  dis[u] = 0;
  par[u] = -1;
  been[u] = true;
  while (me.size()) {
    while (me.size()) {
      int v = me.top();
      me.pop();
      for (auto q : adj[v]) {
        if (!been[q]) {
          you.push(q);
          been[q] = 1;
          dis[q] = dis[v] + 1;
          par[q] = v;
        } else if (q != par[v]) {
          ans = min(ans, dis[q] + dis[v] + 1);
        }
      }
    }
    swap(me, you);
  }
}