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 lp[1000000 + 5], dist[1000000 + 5];
vector<int> d[1000000 + 5], v[1000000 + 5], pr;
vector<vector<int> > e;
int main() {
  pr.push_back(1);
  for (int i = 2; i <= 1000000; i++) {
    if (!lp[i]) {
      pr.push_back(i);
      for (int j = i; j <= 1000000; j += i) lp[j] = i;
    }
    d[i] = d[i / lp[i]];
    auto it = find(d[i].begin(), d[i].end(), lp[i]);
    if (it != d[i].end())
      d[i].erase(it);
    else
      d[i].push_back(lp[i]);
  }
  int n, ans = 1e9;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    int a;
    scanf("%d", &a);
    if (d[a].empty()) {
      printf("1");
      return 0;
    }
    if (d[a].size() == 1) d[a].push_back(1);
    e.push_back({d[a][0], d[a][1]});
    v[d[a][0]].push_back(i);
    v[d[a][1]].push_back(i);
  }
  for (int i : pr) {
    if (i * i > 1000000) break;
    for (int j : pr) dist[j] = 0;
    queue<pair<int, int> > q;
    for (int j : v[i]) {
      q.push({j, (e[j][0] == i)});
      dist[e[j][0] ^ e[j][1] ^ i] = 1;
    }
    while (!q.empty()) {
      auto p = q.front();
      q.pop();
      int node = e[p.first][p.second];
      for (int u : v[node]) {
        if (u != p.first) {
          pair<int, int> np(u, (e[u][0] == node));
          int nnode = e[np.first][np.second];
          if (!dist[nnode] && nnode != i) {
            q.push(np);
            dist[nnode] = dist[node] + 1;
          } else
            ans = min(ans, dist[node] + dist[nnode] + 1);
        }
      }
    }
  }
  if (ans == 1e9) ans = -1;
  printf("%d", ans);
}