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 Np = 2000;
int prime[Np + 5], cntp;
bool notp[Np + 5] = {true, true};
void find_prime(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!notp[i]) prime[++cntp] = i;
    for (int j = 1; j <= cntp && i * prime[j] <= n; ++j) {
      notp[i * prime[j]] = true;
      if (!(i % prime[j])) break;
    }
  }
}
const int N = 1000000;
vector<int> G[N + 5];
int ans, dep[N + 5];
bool vis[N + 5];
void bfs(int u, int fa) {
  queue<pair<int, int>> Q;
  Q.push({u, fa});
  vis[u] = true;
  dep[u] = dep[fa] + 1;
  while (!Q.empty()) {
    u = Q.front().first;
    fa = Q.front().second;
    Q.pop();
    for (int v : G[u])
      if (v != fa) {
        if (!vis[v]) {
          Q.push({v, u});
          vis[v] = true;
          dep[v] = dep[u] + 1;
        } else
          ans = min(ans, dep[u] + dep[v] - 1);
      }
  }
}
int main() {
  find_prime(Np);
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    int u = 1, v = 1, lmt = sqrt(x + 0.5);
    for (int j = 1; prime[j] <= lmt; ++j) {
      if (x % prime[j] == 0) {
        int cnt = 0;
        while (x % prime[j] == 0) {
          x /= prime[j];
          ++cnt;
        }
        if (cnt & 1) {
          if (u == 1)
            u = prime[j];
          else
            v = prime[j];
        }
      }
    }
    if (x != 1) {
      if (u == 1)
        u = x;
      else
        v = x;
    }
    G[u].push_back(v);
    G[v].push_back(u);
  }
  ans = INT_MAX;
  for (int i = 1; i <= 1000; ++i) {
    if (!G[i].empty()) {
      memset(vis, false, sizeof(vis));
      bfs(i, 0);
    }
  }
  if (ans == INT_MAX) ans = -1;
  printf("%d\n", ans);
  return 0;
}