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")
#pragma GCC optimize("Ofast")
using namespace std;
const long long inf = 1e9;
const long long maxa = 1e6 + 100;
const long long block = 1e3 + 100;
const long long maxn = maxa;
long long n, m, k, t;
bool prime[maxa];
vector<long long> dels[maxa];
void sieve() {
  long long q, w;
  for (q = 2; q < maxa; q++) {
    prime[q] = 1;
  }
  for (q = 2; q < maxa; q++) {
    if (!prime[q]) {
      continue;
    }
    for (w = q; w < maxa; w += q) {
      long long w1 = w;
      while (w1 % q == 0) {
        w1 /= q;
        dels[w].push_back(q);
      }
      prime[w] = 0;
    }
  }
}
long long A[maxn];
vector<long long> V[maxn];
bool cool[maxn];
long long D[maxn];
long long P[maxn];
int main() {
  long long q, w, e, a, b, c, d;
  ios_base ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  sieve();
  cin >> n;
  long long ans = inf;
  for (q = 0; q < n; q++) {
    cin >> A[q];
    map<long long, long long> M;
    for (w = 0; w < dels[A[q]].size(); w++) {
      long long del = dels[A[q]][w];
      M[del]++;
    }
    vector<long long> X;
    for (auto p : M) {
      if (p.second % 2 == 1) {
        X.push_back(p.first);
      }
    }
    if (X.size() == 0) {
      cout << 1;
      return 0;
    }
    if (X.size() == 1) {
      if (cool[X[0]]) {
        ans = min(ans, 2LL);
      }
      cool[X[0]] = 1;
    } else {
      long long v = X[0], u = X[1];
      V[v].push_back(u);
      V[u].push_back(v);
    }
  }
  queue<long long> Q;
  for (q = 0; q < maxn; q++) {
    if (cool[q]) {
      Q.push(q);
    } else {
      D[q] = -1;
    }
  }
  while (!Q.empty()) {
    long long v = Q.front();
    Q.pop();
    for (auto v1 : V[v]) {
      if (v1 == P[v]) {
        continue;
      }
      if (D[v1] == -1) {
        P[v1] = v;
        D[v1] = D[v] + 1;
        Q.push(v1);
      } else {
        ans = min(ans, D[v1] + D[v] + 3);
      }
    }
  }
  for (q = 0; q < block; q++) {
    if (V[q].size() >= 2) {
      for (w = 0; w < maxn; w++) {
        D[w] = -1;
      }
      D[q] = 0;
      queue<long long> Q;
      Q.push(q);
      while (!Q.empty()) {
        long long v = Q.front();
        Q.pop();
        for (auto v1 : V[v]) {
          if (v1 == P[v]) {
            continue;
          }
          if (D[v1] == -1) {
            P[v1] = v;
            D[v1] = D[v] + 1;
            Q.push(v1);
          } else {
            ans = min(ans, D[v1] + D[v] + 1);
          }
        }
      }
    }
  }
  if (ans == inf) {
    cout << -1;
    return 0;
  }
  cout << ans;
  return 0;
}