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 INF = 2139062143;
template <typename T>
void read(T &x) {
  x = 0;
  bool f = 1;
  char ch;
  do {
    ch = getchar();
    if (ch == '-') f = 0;
  } while (ch > '9' || ch < '0');
  do {
    x = x * 10 + ch - '0';
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  x = f ? x : -x;
}
template <typename T>
void write(T x) {
  if (x < 0) x = ~x + 1, putchar('-');
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
const int N = 1E5 + 7;
const int M = 1e3 + 7;
int n, ans, fa[N], vis[M];
vector<int> G[M * M];
inline void addedge(int u, int v) {
  G[u].push_back(v);
  G[v].push_back(u);
}
inline void work(int x) {
  if (x == 1) {
    puts("1");
    exit(0);
  }
  vector<int> v;
  v.clear();
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      int ret = 0;
      while (x % i == 0) x /= i, ret++;
      if (ret & 1) v.push_back(i);
    }
  }
  if (x != 1) v.push_back(x);
  while (v.size() < 2) v.push_back(1);
  addedge(v[0], v[1]);
}
inline void BFS(int s) {
  queue<pair<int, int> > q;
  vector<int> d(1e6, -1);
  d[s] = 0;
  q.push(make_pair(s, -1));
  while (!q.empty()) {
    pair<int, int> p = q.front();
    q.pop();
    int u = p.first, fa = p.second;
    for (int i = 0; i < G[u].size(); i++) {
      int v = G[u][i];
      if (d[v] == -1) {
        d[v] = d[u] + 1;
        q.push(make_pair(v, u));
      } else if (v != fa)
        ans = min(ans, d[u] + d[v] + 1);
    }
  }
}
int main() {
  read(n);
  for (int i = 1, x; i <= n; i++) {
    read(x);
    work(x);
  }
  ans = INF;
  for (int i = 1; i <= 1000; i++)
    if (G[i].size()) BFS(i);
  printf("%d\n", ans == INF ? -1 : ans);
  return 0;
}