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;
int a[100005];
vector<int> ps[100005 * 10];
vector<pair<int, int>> edges[100005 * 10];
int fp[100005 * 10];
int dis[100005 * 10];
int bfs(int u) {
  queue<pair<int, int>> q;
  dis[u] = 0;
  for (auto v : edges[u]) {
    q.push(v);
    if (v.first == u) return 1;
    dis[v.first] = 1;
  }
  int res = -1;
  while (!q.empty()) {
    auto cur = q.front();
    q.pop();
    int v = cur.first;
    int p = cur.second;
    for (auto v2 : edges[v]) {
      if (v2.second == p) continue;
      if (dis[v2.first] < 0 && v2.first != u) {
        dis[v2.first] = dis[v] + 1;
        q.push(v2);
      } else {
        res = (res < 0 ? dis[v2.first] + dis[v] + 1
                       : min(res, dis[v2.first] + dis[v] + 1));
      }
    }
  }
  return res;
}
int main() {
  vector<int> prs;
  prs.clear();
  prs.push_back(1);
  for (int i = 2; i <= 1000000; ++i) {
    if (!fp[i]) {
      prs.push_back(i);
      for (int j = i; j <= 1000000; j += i) {
        fp[j] = i;
      }
    }
    ps[i] = ps[i / fp[i]];
    auto itr = find(ps[i].begin(), ps[i].end(), fp[i]);
    if (itr == ps[i].end()) {
      ps[i].push_back(fp[i]);
    } else {
      ps[i].erase(itr);
    }
  }
  scanf("%d", &n);
  int maxv = 0;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    maxv = max(maxv, a[i]);
  }
  for (int i = 1; i <= n; ++i) {
    if (ps[a[i]].size() < 2) {
      ps[a[i]].push_back(1);
    }
    if (ps[a[i]].size() < 2) {
      ps[a[i]].push_back(1);
    }
    int p1 = ps[a[i]][0];
    int p2 = ps[a[i]][1];
    edges[p1].push_back(make_pair(p2, i));
    edges[p2].push_back(make_pair(p1, i));
  }
  int ans = -1;
  for (int v : prs) {
    if (v * v > maxv) {
      break;
    }
    for (int v2 : prs) {
      dis[v2] = -1;
    }
    int res = bfs(v);
    if (res >= 0) {
      ans = (ans < 0 ? res : min(ans, res));
    }
  }
  printf("%d\n", ans);
  return 0;
}