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 optimize GCC("Ofast")
const long long INF = 1e9 + 7;
const long long maxn = 2e6 + 7;
using namespace std;
std::vector<long long> genPrimes() {
  std::vector<long long> primes;
  primes.push_back(2);
  for (long long i = 3; i <= 1000001; i++) {
    bool isPrime = true;
    long long cap = sqrt(i) + 1;
    for (auto prNum = primes.begin(); prNum != primes.end(); prNum++) {
      if (*prNum > cap) {
        break;
      }
      if (i % *prNum == 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime) {
      primes.push_back(i);
    }
  }
  return primes;
}
long long n;
vector<long long> a;
vector<int> adj[maxn];
int findShortestCycle(vector<long long>& runOn) {
  long long maxEl = *max_element(a.begin(), a.end());
  long long ans = LLONG_MAX;
  for (auto s : runOn) {
    if (s * s > maxEl) break;
    queue<int> q;
    vector<int> par(maxEl + 1, -1);
    vector<long long> dist(maxEl + 1, INF);
    dist[s] = 0;
    q.push(s);
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      for (auto y : adj[x]) {
        if (dist[y] == INF) {
          dist[y] = dist[x] + 1;
          par[y] = x;
          q.push(y);
        } else if (par[y] != x && par[x] != y) {
          ans = min(ans, dist[x] + dist[y] + 1);
        }
      }
    }
  }
  return (ans == LLONG_MAX ? -1 : ans);
}
void addEdge(int u, int v) {
  adj[u].push_back(v);
  adj[v].push_back(u);
}
void solve() {
  auto primes = genPrimes();
  cin >> n;
  a.resize(n);
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
  }
  set<long long> s;
  long long ans = LLONG_MAX;
  for (long long i = 0; i < n; i++) {
    long long p1 = 0;
    long long p2 = 0;
    long long temp = a[i];
    for (auto x : primes) {
      if (x * x > a[i]) break;
      if (a[i] % x == 0) {
        if (!p1) {
          p1 = x;
        } else {
          p2 = x;
        }
        while ((a[i] % (x * x)) == 0) {
          a[i] /= (x * x);
        }
      }
    }
    if ((p1 * p2) == 0 && a[i] != 1) {
      if (!p1) {
        p1 = a[i];
      } else {
        p2 = ((a[i] % p1) ? (a[i]) : (a[i] / p1));
      }
    }
    if (a[i] == 1) {
      ans = 1;
      continue;
    }
    long long toInsert;
    if (a[i] == p1) {
      toInsert = p1;
      addEdge(p1, 1);
    } else if (a[i] == p2) {
      toInsert = p2;
      addEdge(p2, 1);
    } else if (a[i] == p1 * p2) {
      toInsert = (p1 * p2);
      addEdge(p1, p2);
    }
    if (s.count(toInsert)) {
      ans = min(ans, 2LL);
      continue;
    } else {
      s.insert(toInsert);
    }
  }
  if (ans != LLONG_MAX) {
    cout << ans << '\n';
    return;
  }
  primes.insert(primes.begin(), 1);
  cout << findShortestCycle(primes) << endl;
}
int main(int argc, char** argv) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T = 1;
  while (T--) {
    solve();
  }
  return 0;
}