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;
template <typename T>
void show(T *a, int size) {
  int i;
  cout << endl << "The array is ";
  for (long long i = 0; i < size; ++i) {
    cout << a[i] << " ";
  }
  cout << endl;
}
template <typename T>
void show_vector(vector<T> v) {
  cout << endl << "The vector is ";
  int i;
  for (long long i = 0; i < v.size(); ++i) {
    cout << v[i] << " ";
  }
  cout << endl;
}
long long int a[100005], n;
vector<long long> factors[1000006];
vector<pair<long long, long long>> adj[1000006];
long long int dist[1000006];
bool is_composite[1000006];
bool odd_pow(long long int j, long long int i) {
  long long int pow = 0;
  while (j % i == 0) {
    j /= i;
    pow++;
  }
  return pow % 2;
}
void factorize_all() {
  for (long long i = 2; i < 1000006; ++i) {
    if (is_composite[i] == 0) {
      factors[i].push_back(1);
      factors[i].push_back(i);
      for (long long int j = 2 * i; j < 1000006; j += i) {
        if (odd_pow(j, i)) factors[j].push_back(i);
        is_composite[j] = 1;
      }
    } else {
      if (factors[i].size() == 1) {
        factors[i].push_back(1);
      }
    }
  }
}
long long int dfs(long long int node) {
  memset(dist, -1, sizeof(dist));
  dist[node] = 0;
  queue<pair<long long, long long>> q;
  q.push({node, -1});
  long long int rv = 1000000007;
  while (!q.empty()) {
    pair<long long, long long> curr = q.front();
    q.pop();
    for (pair<long long, long long> adja : adj[curr.first]) {
      if (adja.second != curr.second) {
        if (dist[adja.first] == -1) {
          q.push(adja);
          dist[adja.first] = dist[curr.first] + 1;
        } else {
          rv = min(rv, dist[adja.first] + dist[curr.first] + 1);
        }
      }
    }
  }
  return rv;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  factorize_all();
  cin >> n;
  long long int max_a = -1;
  long long int flag = 0;
  long long int curr_edge_no = 0;
  for (long long i = 0; i < n; ++i) {
    cin >> a[i];
    max_a = max(max_a, a[i]);
    if (factors[a[i]].size() == 0) {
      flag = 1;
    } else {
      adj[factors[a[i]][1]].push_back({factors[a[i]][0], curr_edge_no});
      adj[factors[a[i]][0]].push_back({factors[a[i]][1], curr_edge_no});
      curr_edge_no++;
    }
  }
  if (flag == 1) {
    cout << "1\n";
    return 0;
  }
  long long int ans = 1000000007;
  for (long long int i = 1; i * i <= max_a + 1; i++) {
    ans = min(dfs(i), ans);
  }
  if (ans != 1000000007) {
    cout << ans << endl;
  } else {
    cout << "-1" << endl;
  }
  return 0;
}