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 eps = 1e-6;
const double Dlt = 0.97;
const int inf = 0x3f3f3f3f;
const long long INF = 2e18;
const int maxn = 1000000 + 10;
const int maxm = 100000 + 10;
const long long mod = 1000000000 + 7;
const long long Mod = 1000000000 + 3;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
inline long long read() {
  char ch = getchar();
  long long x = 0, f = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, id;
int head[maxn], ver[maxn * 2], Next[maxn * 2], edge[maxn * 2], tot;
void add(int u, int v, int w) {
  ++tot;
  ver[tot] = v;
  edge[tot] = w;
  Next[tot] = head[u];
  head[u] = tot;
}
bool isprime(int n) {
  for (int j = 2; j * j <= n; ++j) {
    if (n % j == 0) return 0;
  }
  return 1;
}
int d[maxn], vis[maxn];
int ans = inf;
void bfs(int st) {
  memset(d, -1, sizeof d);
  for (int i = 1; i <= id; ++i) vis[i] = 0;
  d[st] = 0;
  queue<int> q;
  q.push(st);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = head[x]; i != -1; i = Next[i]) {
      if (vis[edge[i]]) continue;
      int y = ver[i];
      vis[edge[i]] = 1;
      if (d[y] == -1) {
        d[y] = d[x] + 1;
        q.push(y);
      } else {
        ans = min(ans, d[y] + d[x] + 1);
      }
    }
  }
}
int main() {
  n = read();
  memset(head, -1, sizeof head);
  for (int i = 1; i <= n; ++i) {
    int x = read();
    int a = 0, b = 1;
    for (int j = 2; j * j <= x; ++j) {
      int cnt = 0;
      while (x % j == 0) {
        x /= j;
        cnt++;
      }
      if (cnt & 1) {
        if (!a)
          a = j;
        else
          b = j;
      }
    }
    if (x > 1) {
      if (!a)
        a = x;
      else
        b = x;
    }
    if (!a) {
      puts("1");
      return 0;
    }
    add(a, b, ++id);
    add(b, a, id);
  }
  for (int i = 1; i <= 1000; ++i) {
    if (isprime(i)) bfs(i);
  }
  if (ans == inf) ans = -1;
  printf("%d\n", ans);
}