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;
void err(istream_iterator<string> it) {}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << a << "\n";
  err(++it, args...);
}
const double PI = acos(-1);
const double eps = (1e-9);
const long long int INF = 2e9;
const int N = (1e6) + 5;
int isprime[N], lowdiv[N];
void factor() {
  int i, a;
  fill(isprime + 2, isprime + N, 1);
  for (i = 2; i * i < N; i++) {
    if (isprime[i]) {
      for (a = i * i; a < N; a += i)
        if (!lowdiv[a]) isprime[a] = 0, lowdiv[a] = i;
    }
  }
  for (i = 2; i < N; i++)
    if (isprime[i]) lowdiv[i] = i;
  return;
}
int convert(int x) {
  int a, p, y = 1;
  while (x > 1) {
    a = lowdiv[x], p = 0;
    while (x % a == 0) x /= a, p++;
    if (p & 1) y *= a;
  }
  return y;
}
vector<vector<int> > ad(N);
vector<int> ar;
int vis[N], lev[N], par[N];
int ans;
void bfs() {
  int s;
  queue<int> pq;
  fill(vis, vis + N, 0);
  fill(lev, lev + N, 0);
  fill(par, par + N, 0);
  for (auto a : ar) pq.push(a), vis[a] = 1;
  while (!pq.empty()) {
    s = pq.front();
    pq.pop();
    for (auto a : ad[s]) {
      if (vis[a] && a == par[s]) continue;
      if (vis[a]) ans = min(ans, lev[a] + lev[s] + 3);
      if (!vis[a]) vis[a] = 1, lev[a] = lev[s] + 1, par[a] = s, pq.push(a);
    }
  }
  return;
}
int v[N];
void cycle(int s) {
  int i, k = 0;
  v[k++] = s;
  queue<int> pq;
  pq.push(s);
  vis[s] = 1;
  while (!pq.empty()) {
    s = pq.front();
    pq.pop();
    for (auto a : ad[s]) {
      if (vis[a] && a == par[s]) continue;
      if (vis[a]) ans = min(ans, lev[a] + lev[s] + 1);
      if (!vis[a])
        vis[a] = 1, lev[a] = lev[s] + 1, par[a] = s, pq.push(a), v[k++] = a;
    }
  }
  for (i = 0; i < k; ++i) s = v[i], vis[s] = 0, lev[s] = 0, par[s] = 0;
  return;
}
void solve() {
  int n, f, i, x, a;
  factor();
  scanf("%d", &n);
  f = 0;
  vector<int> v(n);
  for (i = 0; i < n; ++i) {
    scanf("%d", &x);
    x = convert(x);
    if (x == 1) f = 1;
    v[i] = x;
  }
  if (f) printf("%d\n", 1), exit(0);
  sort(v.begin(), v.end());
  for (i = 0; i < n - 1; ++i)
    if (v[i] == v[i + 1]) printf("%d\n", 2), exit(0);
  for (i = 0; i < n; ++i) {
    a = v[i];
    if (!isprime[a]) {
      x = lowdiv[a];
      ad[x].emplace_back(a / x);
      ad[a / x].emplace_back(x);
    } else
      ar.emplace_back(a);
  }
  ans = N;
  bfs();
  for (i = 0; i < N; ++i) vis[i] = 0, par[i] = 0, lev[i] = 0;
  for (i = 0; i < 1000; ++i) cycle(i);
  if (ans == N) ans = -1;
  printf("%d\n", ans);
}
int main() {
  int t = 1;
  while (t--) solve();
}