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>
#pragma GCC optimize("Ofast")
using namespace std;
vector<int> v[1000005];
int f[1000005], step[1000005];
void dfs(int p) {
  step[p] = 1e9;
  f[p] = -1;
  for (auto u : v[p])
    if (step[u] < 1e9) dfs(u);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, x, t, l;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    t = x;
    vector<int> s;
    for (int j = 2; j * j <= x; j++) {
      if (t % j == 0) {
        l = 0;
        while (t % j == 0) {
          t /= j;
          l++;
        }
        if (l & 1) s.emplace_back(j);
      }
    }
    if (t != 1) s.emplace_back(t);
    if (!s.size()) {
      cout << 1;
      return 0;
    }
    if (s.size() == 1) {
      v[1].emplace_back(s[0]);
      v[s[0]].emplace_back(1);
    } else {
      v[s[0]].emplace_back(s[1]);
      v[s[1]].emplace_back(s[0]);
    }
  }
  memset(f, -1, sizeof(f));
  int cur, ans = 1e9;
  bool ag;
  for (int i = 1; i <= 1000; i++) {
    queue<int> q;
    q.emplace(i);
    dfs(i);
    step[i] = 0;
    while (!q.empty()) {
      cur = q.front();
      q.pop();
      ag = 1;
      for (auto u : v[cur]) {
        if (step[u] == 1e9) {
          f[u] = cur;
          step[u] = step[cur] + 1;
          q.emplace(u);
        } else {
          if (f[cur] == u && ag)
            ag = 0;
          else
            ans = min(ans, step[cur] + step[u] + 1);
        }
      }
    }
  }
  if (ans == 1e9) {
    cout << -1;
  } else
    cout << ans;
  return 0;
}