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 N = 2e5 + 5;
const int M = 1e6 + 1;
vector<int> dvs[M];
vector<int> prs;
vector<int> g[N];
int d[N];
int p[N];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for (int i = 2; i < M; ++i)
    if (dvs[i].empty())
      for (int j = i; j < M; j += i) dvs[j].emplace_back(i);
  for (int i = 2; i < M; ++i)
    if (dvs[i][0] == i) prs.emplace_back(i);
  int n;
  cin >> n;
  bool ok = 0;
  set<pair<int, int> > S;
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    vector<int> vec;
    while (x > 1) {
      int p = dvs[x][0];
      int e = 0;
      while (x % p == 0) x /= p, e ^= 1;
      if (e) vec.emplace_back(p);
    }
    if (vec.empty()) {
      cout << 1;
      return 0;
    }
    int a = upper_bound(prs.begin(), prs.end(), vec[0]) - prs.begin();
    int b = upper_bound(prs.begin(), prs.end(), vec.size() > 1 ? vec[1] : 0) -
            prs.begin();
    if (S.find(pair<int, int>(a, b)) != S.end()) {
      ok = 1;
      continue;
    }
    S.insert(pair<int, int>(a, b));
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  if (ok) {
    cout << 2;
    return 0;
  }
  int ans = 1e9;
  for (int i = 1; i <= (int)prs.size(); ++i) {
    if (prs[i - 1] > 1000) break;
    fill(d, d + 1 + (int)prs.size(), -1);
    fill(p, p + 1 + (int)prs.size(), -1);
    queue<int> qu;
    d[i] = 0;
    qu.push(i);
    while (qu.size()) {
      int u = qu.front();
      qu.pop();
      for (int v : g[u])
        if (d[v] < 0) p[v] = u, d[v] = d[u] + 1, qu.push(v);
    }
    for (pair<int, int> e : S) {
      int x = e.first;
      int y = e.second;
      if (d[x] < 0) continue;
      if (d[y] < 0) continue;
      if (x == p[y]) continue;
      if (y == p[x]) continue;
      ans = min(ans, d[x] + d[y] + 1);
    }
  }
  if (ans == 1e9) ans = -1;
  cout << ans << endl;
}