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 MAXN = 100005;
const int MAXA = 1000005;
const int MAXS = 1005;
const int INF = 0x3f3f3f3f;
int a[MAXN];
vector<int> e[MAXA];
int calc(int x) {
  for (int i = 2; i * i <= x; i++)
    if (x % i == 0) {
      int cnt = 0;
      while (x % i == 0) x /= i, cnt++;
      if (cnt & 1) x *= i;
    }
  return x;
}
int inq[MAXA], dis[MAXA];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i] = calc(a[i]);
  sort(a + 1, a + n + 1);
  if (a[1] == 1) return 0 * printf("1\n");
  if (unique(a + 1, a + n + 1) - (a + 1) < n) return 0 * printf("2\n");
  vector<int> val;
  for (int i = 1; i <= n; i++) {
    vector<int> p;
    for (int j = 2; j * j <= a[i]; j++)
      if (a[i] % j == 0) {
        p.push_back(j);
        while (a[i] % j == 0) a[i] /= j;
      }
    if (a[i] > 1) p.push_back(a[i]);
    while ((int)p.size() < 2) p.push_back(1);
    int u = p[0], v = p[1];
    e[u].push_back(v);
    e[v].push_back(u);
    val.push_back(u);
    val.push_back(v);
  }
  sort(val.begin(), val.end());
  val.erase(unique(val.begin(), val.end()), val.end());
  int res = INF;
  for (int i = 1; i < MAXS; i++) {
    if (e[i].empty()) continue;
    for (auto& u : val) inq[u] = 0, dis[u] = INF;
    queue<int> q;
    q.push(i);
    inq[i] = 1, dis[i] = 0;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      inq[u] = 0;
      for (auto& v : e[u]) {
        if (dis[v] > dis[u] + 1) {
          inq[v] = 1;
          dis[v] = dis[u] + 1;
          q.push(v);
        } else if (inq[v])
          res = min(res, dis[u] + dis[v] + 1);
      }
    }
  }
  return 0 * printf("%d\n", (res < INF ? res : -1));
}