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 INF = 0x3f3f3f3f;
const long long int llINF = (long long)(1e18) + 100;
const long long int MAXN = 1e6 + 10;
int lp[MAXN];
vector<int> pr;
void crivo() {
  for (long long int i = 2; i < MAXN; i++) {
    if (lp[i] == 0) {
      lp[i] = i;
      pr.push_back(i);
    }
    for (long long int j = 0;
         j < (int)pr.size() && pr[j] <= lp[i] && i * pr[j] < MAXN; ++j)
      lp[i * pr[j]] = pr[j];
  }
}
int n, dist[MAXN];
vector<int> adj[MAXN], dcp[MAXN];
vector<pair<int, int> > edge;
int other(int idx, int u) {
  return edge[idx].first == u ? edge[idx].second : edge[idx].first;
}
int bfs(int p) {
  memset(dist, 0, sizeof(dist));
  queue<pair<int, int> > fila;
  for (int x : adj[p]) {
    fila.push({x, other(x, p)});
    dist[other(x, p)] = 1;
  }
  int u, v, ans = INF;
  pair<int, int> aux;
  while (!fila.empty()) {
    aux = fila.front();
    fila.pop();
    u = aux.second;
    for (int w : adj[u]) {
      if (w != aux.first) {
        v = other(w, u);
        if (dist[v] == 0 and v != p) {
          fila.push({w, v});
          dist[v] = dist[u] + 1;
        } else
          ans = min(ans, dist[u] + dist[v] + 1);
      }
    }
  }
  return ans;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  crivo();
  lp[1] = 1;
  cin >> n;
  for (int i = 2; i < MAXN; i++) {
    dcp[i] = dcp[i / lp[i]];
    auto it = find(dcp[i].begin(), dcp[i].end(), lp[i]);
    if (it != dcp[i].end())
      dcp[i].erase(it);
    else
      dcp[i].push_back(lp[i]);
  }
  int a;
  for (int i = 0; i < n; i++) {
    cin >> a;
    if (dcp[a].empty()) {
      cout << 1 << '\n';
      return 0;
    }
    if (dcp[a].size() == 1) dcp[a].push_back(1);
    edge.push_back({dcp[a][0], dcp[a][1]});
    adj[dcp[a][0]].push_back(i);
    adj[dcp[a][1]].push_back(i);
  }
  int ans = INF;
  pr.insert(pr.begin(), 1);
  for (int p : pr) {
    if (p * p > MAXN) break;
    ans = min(ans, bfs(p));
  }
  cout << (ans == INF ? -1 : ans) << '\n';
}