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;
int n;
vector<int> a;
const int MAX_PRIME = 1e6;
vector<int> g[MAX_PRIME];
int divisors[MAX_PRIME] = {0}, primes[MAX_PRIME] = {0}, nPrimes = 0;
void generatePrimes() {
  for (int i = 2; i < MAX_PRIME; i++) {
    if (divisors[i] == 0) divisors[i] = primes[nPrimes++] = i;
    for (int j = 0; j < nPrimes && i * primes[j] < MAX_PRIME; j++)
      divisors[i * primes[j]] = min(divisors[i], primes[j]);
  }
}
map<long long, int> factorize(long long x) {
  map<long long, int> res;
  for (int i = 0; 1ll * primes[i] * primes[i] <= x; i++) {
    if (x % primes[i] == 0) {
      int c = 0;
      while (x % primes[i] == 0) c++, x /= primes[i];
      res[primes[i]] = c;
    }
  }
  if (x != 1) res[x] = 1;
  return res;
}
int main() {
  generatePrimes();
  while (scanf("%d", &n) == 1) {
    for (int i = 0; i < MAX_PRIME; i++) g[i].clear();
    a.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];
    int res = 1e9;
    set<int> isTerm;
    for (auto &x : a) {
      auto f = factorize(x);
      vector<int> vs;
      for (auto &p : f)
        if (p.second % 2) vs.push_back(p.first);
      if (vs.size() == 0) {
        res = 1;
      } else if (vs.size() == 1) {
        g[1].push_back(vs[0]);
        g[vs[0]].push_back(1);
      } else {
        g[vs[0]].push_back(vs[1]);
        g[vs[1]].push_back(vs[0]);
      }
    }
    vector<int> d(MAX_PRIME, -1);
    for (int p = 1; p <= 1000; p++) {
      if (p != 1 && divisors[p] != p) continue;
      queue<int> q;
      q.push(p);
      d[p] = 0;
      vector<int> vis;
      int cFound = false;
      while (!q.empty() && !cFound) {
        int v = q.front();
        q.pop();
        vis.push_back(v);
        for (auto &to : g[v]) {
          if (d[to] != -1 && d[to] + 1 != d[v]) {
            res = min(res, d[to] + d[v] + 1);
            break;
          }
          if (d[to] != -1) continue;
          d[to] = d[v] + 1;
          q.push(to);
        }
      }
      for (auto &x : vis) d[x] = -1;
    }
    printf("%d\n", res == 1e9 ? -1 : res);
  }
  return 0;
}