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 = 1e6 + 5;
int n;
int a[N];
vector<int> edge[N];
bool zihuan[N];
bool not_prime[N];
int prime[N], cnt = 0;
void sss(int n) {
  for (int i = 2; i <= n; i++) {
    if (not_prime[i] == 0) prime[++cnt] = i;
    for (int j = 1; j <= cnt && i * 1ll * prime[j] <= n; j++) {
      not_prime[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
}
queue<int> que;
int pre[N];
int dep[N];
int LIAN[2], HUAN;
int check(int be) {
  for (int i = 1; i <= cnt; i++) dep[prime[i]] = pre[prime[i]] = -1;
  while (!que.empty()) que.pop();
  int tot = 0;
  LIAN[0] = LIAN[1] = HUAN = INT_MAX;
  que.push(be);
  dep[be] = 0;
  if (zihuan[be]) LIAN[tot++] = 0;
  while (!que.empty()) {
    auto now = que.front();
    que.pop();
    for (auto &it : edge[now]) {
      if (it == pre[now]) continue;
      if (dep[it] >= 0) {
        HUAN = min(HUAN, dep[it] + dep[now] + 1);
        continue;
      }
      dep[it] = dep[now] + 1;
      que.push(it);
      pre[it] = now;
      if (tot < 2 && zihuan[it]) {
        LIAN[tot++] = dep[it];
      }
    }
  }
  int tmp = INT_MAX;
  if (HUAN >= 0) tmp = HUAN;
  if (tot == 2) tmp = min(LIAN[0] + LIAN[1] + 2, tmp);
  return tmp;
}
int main() {
  ios::sync_with_stdio(false);
  sss(1000000);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    for (int j = 2; j * j <= a[i]; j++) {
      while (a[i] % (j * j) == 0) {
        a[i] /= (j * j);
      }
    }
  }
  sort(a + 1, a + n + 1);
  if (a[1] == 1) {
    cout << "1\n";
    return 0;
  }
  for (int i = 1; i < n; i++)
    if (a[i] == a[i + 1]) {
      cout << "2\n";
      return 0;
    }
  for (int i = 1; i <= n; i++) {
    if (not_prime[a[i]] == 0) {
      zihuan[a[i]] = 1;
    } else {
      for (int j = 1; prime[j] <= a[i]; j++) {
        if (a[i] % prime[j] == 0) {
          int x = prime[j];
          int y = a[i] / prime[j];
          edge[x].emplace_back(y);
          edge[y].emplace_back(x);
          break;
        }
      }
    }
  }
  int ans = INT_MAX;
  for (int i = 1; prime[i] <= 1000 && prime[i] <= a[n]; i++) {
    if (edge[prime[i]].empty()) continue;
    ans = min(ans, check(prime[i]));
  }
  if (ans == INT_MAX) ans = -1;
  cout << ans << endl;
}