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;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 100005, M = 1000006;
int u[M];
void pre() {
  for (int i = 2; i < M; ++i) {
    if (u[i]) continue;
    for (int j = i; j < M; j += i) {
      if (!u[j]) u[j] = i;
    }
  }
}
int n;
int a[N];
pair<int, int> b[N];
int qq[M];
vector<int> g[M];
vector<int> gi[M];
int c[M];
int d[M];
int ans1() {
  memset(c, 0, sizeof c);
  memset(d, 0, sizeof d);
  queue<int> q;
  for (int i = 0; i < M; ++i) {
    if (qq[i]) {
      c[i] = i;
      d[i] = 0;
      q.push(i);
    }
  }
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = 0; i < g[x].size(); ++i) {
      int h = g[x][i];
      if (!c[h]) {
        c[h] = c[x];
        d[h] = d[x] + 1;
        q.push(h);
      }
    }
  }
  int ans = M;
  for (int i = 1; i <= n; ++i) {
    if (b[i].first == -1) continue;
    if (c[b[i].first] != c[b[i].second])
      ans = min(ans, d[b[i].first] + 3 + d[b[i].second]);
  }
  return ans;
}
int pi[M];
int bfs(int s) {
  vector<int> v;
  queue<int> q;
  c[s] = 1;
  d[s] = 0;
  q.push(s);
  pi[s] = 0;
  v.push_back(s);
  int ans = M;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = 0; i < g[x].size(); ++i) {
      int h = g[x][i];
      if (!c[h]) {
        c[h] = 1;
        d[h] = d[x] + 1;
        q.push(h);
        v.push_back(h);
        pi[h] = gi[x][i];
      } else if (gi[x][i] != pi[x] && pi[h] != gi[x][i])
        ans = min(ans, d[x] + d[h] + 1);
    }
  }
  for (int i = 0; i < v.size(); ++i) c[v[i]] = 0;
  return ans;
}
int ans2() {
  memset(c, 0, sizeof c);
  int ans = M;
  for (int i = 1; i <= 1000; ++i) {
    if (u[i] == i) {
      ans = min(ans, bfs(i));
    }
  }
  return ans;
}
void solv() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1; i <= n; ++i) {
    set<int> s;
    int x = a[i];
    while (x > 1) {
      if (s.find(u[x]) == s.end())
        s.insert(u[x]);
      else
        s.erase(u[x]);
      x /= u[x];
    }
    if (s.empty()) {
      printf("1\n");
      return;
    } else if (s.size() == 1) {
      ++qq[*s.begin()];
      b[i].first = b[i].second = -1;
    } else {
      b[i].first = *s.begin();
      b[i].second = *(++s.begin());
      g[b[i].first].push_back(b[i].second);
      g[b[i].second].push_back(b[i].first);
      gi[b[i].first].push_back(i);
      gi[b[i].second].push_back(i);
    }
  }
  for (int i = 0; i < M; ++i) {
    if (qq[i] > 1) {
      printf("2\n");
      return;
    }
  }
  int ans = M;
  ans = min(ans, ans1());
  ans = min(ans, ans2());
  if (ans == M)
    printf("-1\n");
  else
    printf("%d\n", ans);
}
int main() {
  pre();
  solv();
  return 0;
}