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>
#pragma GCC optimize(2)
using namespace std;
const int man = 1e6 + 10;
template <typename T>
inline T read() {
  T sum = 0, fl = 1;
  int ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') fl = -1;
  for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
  return sum * fl;
}
template <typename T>
inline void write(T x) {
  static int sta[35];
  int top = 0;
  do {
    sta[top++] = x % 10, x /= 10;
  } while (x);
  while (top) putchar(sta[--top] + 48);
}
template <typename T>
T gcd(T a, T b) {
  return b == 0 ? a : gcd(b, a % b);
}
template <typename T>
T exgcd(T a, T b, T &g, T &x, T &y) {
  if (!b) {
    g = a, x = 1, y = 0;
  } else {
    exgcd(b, a % b, g, y, x);
    y -= x * (a / b);
  }
}
const long long mod = 1e9 + 7;
int a[man / 10];
bool vis_a[man];
vector<int> fac[man], sp[man], fac_;
int dis[man], vis[man];
const int inf = 0x3f3f3f3f;
void init(int maxx) {
  for (int i = 1; i <= maxx; i++) {
    for (int j = i; j <= maxx; j += i) {
      fac[j].push_back(i);
    }
  }
}
int _(int x) {
  int ans = 1;
  for (int i = 2; 1ll * i * i <= x; i++) {
    if (x % i == 0) {
      int cnt = 0;
      while (x % i == 0) x /= i, cnt++;
      if (cnt & 1) ans *= i;
    }
  }
  if (x != 1) ans *= x;
  return ans;
}
int ans = INT_MAX;
void bfs(int s) {
  for (int i = 0; i < fac_.size(); i++) dis[fac_[i]] = inf, vis[fac_[i]] = 0;
  queue<int> q;
  q.push(s);
  vis[s] = 1;
  dis[s] = 0;
  while (q.size()) {
    int u = q.front();
    q.pop();
    vis[u] = 0;
    for (int i = 0; i < sp[u].size(); i++) {
      int v = sp[u][i];
      if (dis[v] > dis[u] + 1) {
        dis[v] = dis[u] + 1;
        vis[v] = 1;
        q.push(v);
      } else if (vis[v])
        ans = min(ans, dis[v] + dis[u] + 1);
    }
  }
}
int main() {
  int n;
  cin >> n;
  int minn = INT_MAX, maxx = -INT_MAX;
  int num = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] = _(a[i]);
    minn = min(minn, a[i]);
    maxx = max(maxx, a[i]);
    if (!vis_a[a[i]]) vis_a[a[i]] = 1, num++;
  }
  if (minn == 1) {
    cout << 1 << endl;
  } else if (num != n) {
    cout << 2 << endl;
  } else {
    init(maxx);
    for (int i = 1; i <= n; i++) {
      if (fac[a[i]].size() == 2) {
        sp[1].push_back(a[i]);
        sp[a[i]].push_back(1);
        fac_.push_back(1);
        fac_.push_back(a[i]);
      } else {
        sp[fac[a[i]][1]].push_back(fac[a[i]][2]);
        sp[fac[a[i]][2]].push_back(fac[a[i]][1]);
        fac_.push_back(fac[a[i]][1]);
        fac_.push_back(fac[a[i]][2]);
      }
    }
    sort(fac_.begin(), fac_.end());
    fac_.erase(unique(fac_.begin(), fac_.end()), fac_.end());
    for (int i = 0; i < 1000; i++) {
      if (!sp[i].size()) continue;
      bfs(i);
    }
    if (ans == INT_MAX) ans = -1;
    cout << ans << endl;
  }
  return 0;
}