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 double PI = atan(1.0) * 4;
const int64_t INF = 1000000000000000003;
const int32_t LOG = 21;
const long long int MOD = 1e9 + 7;
long long int a[100005];
pair<long long int, long long int> b[100005];
vector<long long int> v[100005];
long long int level[100005];
long long int ind[1000005];
bool checker[1000005];
bool check[100005];
long long int loc[100005];
long long int n;
long long int shortest_cycle(long long int n) {
  long long int ans = INT_MAX;
  for (long long int i = 0; i < n; i++) {
    long long int temp = loc[i];
    if (temp * temp >= 1000001) continue;
    vector<long long int> dist(n, (long long int)(1e9));
    vector<long long int> par(n, -1);
    dist[i] = 0;
    queue<long long int> q;
    q.push(i);
    while (!q.empty()) {
      long long int x = q.front();
      q.pop();
      for (long long int child : v[x]) {
        if (dist[child] == (long long int)(1e9)) {
          dist[child] = 1 + dist[x];
          par[child] = x;
          q.push(child);
        } else if (par[x] != child and par[child] != x)
          ans = min(ans, dist[x] + dist[child] + 1);
      }
    }
  }
  if (ans == INT_MAX)
    return -1;
  else
    return ans;
}
int32_t main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  long long int tests = 1;
  for (long long int ii = 0; ii < tests; ii++) {
    cin >> n;
    long long int pos = 2;
    ind[0] = 1;
    loc[0] = 1;
    bool g = false;
    for (long long int i = 0; i < n; i++) cin >> a[i];
    for (long long int i = 0; i < n; i++) {
      b[i] = {1, 1};
      long long int cur = 0;
      for (long long int j = 2; j * j <= a[i]; j++) {
        if (a[i] % j == 0) {
          long long int cnt = 0;
          while (a[i] % j == 0) {
            a[i] /= j;
            cnt++;
          }
          if (!cur && (cnt & 1)) {
            b[i].first = j;
            cur++;
          } else if (cnt & 1)
            b[i].second = j;
        }
      }
      if (a[i] != 1) {
        if (!cur)
          b[i].first = a[i];
        else
          b[i].second = a[i];
      }
      long long int normalized = b[i].first * b[i].second;
      if (checker[normalized]) {
        g = true;
      }
      checker[normalized] = true;
      if (b[i].first == 1) {
        cout << 1 << '\n';
        return 0;
      }
      if (b[i].first != 1) {
        if (ind[b[i].first] != 0) {
        } else {
          ind[b[i].first] = pos;
          loc[pos] = b[i].first;
          pos++;
        }
      }
      if (b[i].second != 1) {
        if (ind[b[i].second] != 0)
          ;
        else {
          ind[b[i].second] = pos;
          loc[pos] = b[i].second;
          pos++;
        }
      }
    }
    if (g) {
      cout << 2 << '\n';
      return 0;
    }
    for (long long int i = 0; i < n; i++) {
      long long int ind1 = ind[b[i].first];
      long long int ind2 = ind[b[i].second];
      v[ind1].push_back(ind2);
      v[ind2].push_back(ind1);
    }
    n = pos;
    long long int ans = shortest_cycle(n);
    cout << ans << '\n';
  }
  return 0;
}