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_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const long long INF = 1e18 + 123;
const long double EPS = 1e-9;
const int inf = 1e9 + 123;
const int MOD = 1e9 + 7;
const int N = 78600;
const int M = 1e6 + 123;
const double pi = 3.14159265359;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
vector<int> g[N];
int lp[M], id[M];
int used[N], d[N], was[N], p[N];
int mx = 1009;
void solve() {
  int P = 1;
  for (int i = 2; i < M; i++) {
    if (!lp[i]) {
      id[i] = ++P;
      for (int j = i; j < M; j += i) {
        if (!lp[j]) lp[j] = i;
      }
    }
  }
  int n, first;
  cin >> n;
  while (n--) {
    cin >> first;
    vector<int> d;
    while (first > 1) {
      int second = lp[first];
      bool c = 0;
      while (first % second == 0) {
        first /= second;
        c ^= 1;
      }
      if (c) d.push_back(id[second]);
    }
    if (d.empty()) {
      cout << 1;
      return;
    } else {
      if ((int)d.size() == 1) d.push_back(1);
      g[d[0]].push_back(d[1]);
      g[d[1]].push_back(d[0]);
    }
  }
  queue<int> q;
  int ans = inf;
  for (int v = 1; v <= mx; v++) {
    sort(g[v].begin(), g[v].end());
    int last = -1;
    for (int u : g[v]) {
      if (last == u) {
        cout << 2;
        return;
      }
      last = u;
    }
    q.push(v);
    used[v] = v;
    d[v] = 0;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int to : g[u]) {
        if (used[to] != v) {
          d[to] = d[u] + 1;
          p[to] = u;
          used[to] = v;
          q.push(to);
        } else if (p[u] != to) {
          ans = min(ans, d[u] + d[to] + 1);
        }
      }
    }
  }
  if (ans == inf) ans = -1;
  cout << ans;
  return;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  for (int i = 1; i <= t; i++) {
    solve();
  }
  return 0;
}