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;
vector<int> prime;
int isprime[1000005];
void Find() {
  for (int i = 2; i < 1000005; i++) {
    if (isprime[i] == 0) {
      prime.push_back(i);
      for (int j = i * 2; j < 1000005; j += i) isprime[j] = 1;
    }
  }
}
vector<int> v[1000005];
int dis[1000005];
int from[1000005];
int main() {
  int n;
  scanf("%d", &n);
  vector<int> vv;
  for (int i = 2; i <= 1000; i++) {
    vv.push_back(i * i);
  }
  vector<int> ok, ok2;
  Find();
  for (int i = 1; i <= n; i++) {
    int first;
    scanf("%d", &first);
    for (auto it : vv) {
      while (first % it == 0) first /= it;
    }
    if (first == 1) {
      printf("1\n");
      return 0;
    }
    if (isprime[first] == 0)
      ok.push_back(first);
    else {
      for (int j = 2; j < 1000; j++) {
        if (first % j == 0) {
          v[first / j].push_back(j);
          v[j].push_back(first / j);
          break;
        }
      }
      ok2.push_back(first);
    }
  }
  sort(ok.begin(), ok.end());
  for (int i = 1; i < ok.size(); i++) {
    if (ok[i] == ok[i - 1]) {
      printf("2\n");
      return 0;
    }
  }
  sort(ok2.begin(), ok2.end());
  for (int i = 1; i < ok.size(); i++) {
    if (ok[i] == ok[i - 1]) {
      printf("2\n");
      return 0;
    }
  }
  queue<int> q;
  memset(dis, -1, sizeof(dis));
  for (auto it : ok) {
    dis[it] = 0;
    q.push(it);
  }
  int ans = 1e9;
  while (!q.empty()) {
    int first = q.front();
    q.pop();
    for (auto it : v[first]) {
      if (dis[it] == -1) {
        dis[it] = dis[first] + 1;
        from[it] = first;
        q.push(it);
      } else {
        if (from[first] == it)
          ;
        else {
          ans = min(ans, dis[it] + dis[first] + 1 + 2);
        }
      }
    }
  }
  for (auto it : prime) {
    if (it > 1000) break;
    for (auto it2 : prime) dis[it2] = -1;
    dis[it] = 0;
    queue<int> q;
    q.push(it);
    while (!q.empty()) {
      int first = q.front();
      q.pop();
      for (auto it2 : v[first]) {
        if (dis[it2] == -1) {
          dis[it2] = dis[first] + 1;
          from[it2] = first;
          q.push(it2);
        } else {
          if (from[first] == it2)
            ;
          else {
            ans = min(ans, dis[first] + dis[it2] + 1);
          }
        }
      }
    }
  }
  if (ans == 1e9) {
    printf("-1\n");
  } else {
    printf("%d\n", ans);
  }
}