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 = 0x3f3f3f3f;
int n;
int a[100000 + 20], depth[100000 + 1000000 + 20];
bool used[1000000 + 100000 + 20];
vector<int> each[1000000 + 20 + 100000];
int res = INF;
void dfs(int now, int deep) {
  depth[now] = deep;
  used[now] = 1;
  for (auto it : each[now]) {
    if (!used[it]) {
      dfs(it, deep + 1);
    }
  }
}
int f[1000000 + 20 + 100000];
bool prim[1000000 + 20];
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  prim[2] = 0;
  for (int i = 2; i <= 1000000; ++i) {
    if (prim[i] == 0) {
      for (int j = i * 2; j <= 1000000; j += i) {
        prim[j] = 1;
      }
    }
  }
  vector<int> ps;
  for (int i = 1; i * i <= 1000000; i++) {
    ps.push_back(i * i);
  }
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    for (int j = 1000; j >= 1; --j) {
      if (a[i] % ps[j - 1] == 0) {
        a[i] /= ps[j - 1];
      }
    }
    if (a[i] == 1) {
      cout << 1 << endl;
      return 0;
    }
    if (f[a[i]]) {
      res = 2;
    }
    f[a[i]] = 1;
    vector<int> pr;
    if (prim[a[i]] == 0) {
      pr.push_back(1);
      pr.push_back(a[i]);
    } else
      for (int k = 2; k * k <= a[i]; k++) {
        if (a[i] % k == 0)
          if (!prim[k]) {
            pr.push_back(k);
            pr.push_back(a[i] / k);
          }
      }
    each[pr[0]].push_back(i + 1000000);
    each[pr[1]].push_back(i + 1000000);
    each[i + 1000000].push_back(pr[0]);
    each[i + 1000000].push_back(pr[1]);
  }
  if (res == 2) {
    cout << 2 << endl;
    return 0;
  }
  for (int i = 1; i <= 1000; ++i) {
    memset(used, 0, sizeof(used));
    queue<int> q;
    q.push(i);
    depth[i] = 1;
    used[i] = 1;
    while (!q.empty()) {
      int now = q.front();
      q.pop();
      int cnt = 0;
      for (auto it : each[now]) {
        if (!used[it]) {
          used[it] = 1;
          q.push(it);
          depth[it] = depth[now] + 1;
        } else {
          if (depth[it] == depth[now] - 1) {
            cnt++;
          }
        }
      }
      if (cnt >= 2) {
        res = min(res, depth[now] - 1);
      }
    }
  }
  if (res == INF) {
    res = -1;
    cout << res << endl;
  } else {
    cout << res << endl;
  }
  return 0;
}