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;
vector<int> prime_factor(int n) {
  vector<int> ret;
  for (int i = 2; i * i <= n; i++) {
    int cnt = 0;
    while (n % i == 0) {
      n /= i;
      cnt++;
    }
    if (cnt % 2) ret.push_back(i);
  }
  if (n > 1) ret.push_back(n);
  return ret;
}
int main() {
  int N;
  cin >> N;
  set<vector<int>> st;
  static vector<int> edges[int(1e6)];
  int ans = 1e9;
  for (int i = 0; i < N; i++) {
    int a;
    scanf("%d", &a);
    auto p = prime_factor(a);
    if (p.size() == 0) {
      ans = 1;
    } else if (st.count(p)) {
      ans = min(ans, 2);
    } else {
      if (p.size() == 1) p.push_back(0);
      edges[p[0]].push_back(p[1]);
      edges[p[1]].push_back(p[0]);
    }
  }
  vector<int> dist(1e6, 1e9);
  for (int s = 0; s <= 1000; s++)
    if (edges[s].size()) {
      fill(dist.begin(), dist.end(), 1e9);
      dist[s] = 0;
      queue<pair<int, int>> que;
      que.emplace(s, -1);
      while (que.size()) {
        auto p = que.front();
        que.pop();
        int i = p.first, par = p.second;
        for (int j : edges[i])
          if (j != par) {
            if (dist[j] == 1e9) {
              dist[j] = dist[i] + 1;
              que.emplace(j, i);
            } else {
              int res = dist[i] + dist[j] + 1;
              ans = min(ans, res);
            }
          }
      }
    }
  if (ans == 1e9) ans = -1;
  cout << ans << endl;
  return 0;
}