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 long long INF = 1E9;
const long long MOD = 1E9 + 7;
const long long N = 2E6 + 5;
long long t = 1;
long long n;
long long p[N], a[N];
vector<long long> SNT[N];
void Input() {
  scanf("%lld", &n);
  for (long long i = 1; i <= n; i++) scanf("%lld", &a[i]);
}
void Prepare() {
  long long tmp = 1e6;
  memset(p, 0, sizeof(p));
  for (long long i = 2; i * i <= tmp; i++)
    if (p[i] == 0) {
      for (long long j = i; i * j <= tmp; j++) p[i * j] = i;
    }
  for (long long i = 1; i <= tmp; i++)
    if (p[i] == 0) p[i] = i;
}
struct canh {
  long long u, v, root;
};
vector<pair<long long, long long> > E;
vector<long long> gr[N];
void Add_edge(long long x, long long y) {
  gr[x].push_back(y);
  gr[y].push_back(x);
}
long long shortest_cycle(long long n) {
  long long ans = 1e9;
  for (long long i = 0; i < min(n, (long long)200); i++) {
    vector<long long> dist(n, (-1));
    vector<long long> par(n, -1);
    dist[i] = 0;
    queue<long long> q;
    q.push(i);
    while (!q.empty()) {
      long long x = q.front();
      q.pop();
      for (long long child : gr[x]) {
        if (dist[child] == (-1)) {
          dist[child] = 1 + dist[x];
          par[child] = x;
          q.push(child);
        } else if (par[x] != child and par[child] != x)
          ans = min(ans, dist[x] + dist[child] + 1);
      }
    }
  }
  if (ans == 1e9)
    return -1;
  else
    return ans;
}
vector<long long> V;
bool avail[N];
long long key[N];
void Solve() {
  for (long long i = 1; i <= n; i++) {
    if (sqrt(a[i]) == trunc(sqrt(a[i]))) {
      cout << 1 << endl;
      return;
    }
  }
  sort(a + 1, a + 1 + n);
  for (int i = 1; i < n; i++)
    if (a[i] == a[i + 1]) {
      cout << 2 << endl;
      return;
    }
  for (long long i = 1; i <= n; i++)
    if (a[i] > 1) {
      long long next = p[a[i]];
      if (next == a[i]) {
        SNT[next].push_back(i);
      } else if (a[i] % (next * next) == 0) {
        SNT[p[a[i] / next / next]].push_back(i);
      } else {
        long long n2 = a[i] / next;
        if (p[n2] == n2) {
          E.push_back({next, n2});
        } else {
          SNT[next].push_back(i);
        }
      }
    }
  for (long long i = 1; i <= 1e6; i++) avail[i] = 0;
  for (long long i = 2; i <= 1e6; i++)
    if (SNT[i].size() >= 2) {
      cout << 2 << endl;
      return;
    } else if (SNT[i].size() == 1) {
      avail[1] = 1;
      avail[i] = 1;
    }
  for (pair<long long, long long> tmp : E) {
    long long u = tmp.first;
    long long v = tmp.second;
    if (SNT[u].size() > 0 && SNT[v].size() > 0) {
      cout << 3 << endl;
      return;
    }
    avail[u] = 1;
    avail[v] = 1;
  }
  n = 0;
  for (long long i = 1; i <= 1e6; i++)
    if (avail[i]) {
      key[i] = n++;
    }
  for (pair<long long, long long> tmp : E) {
    long long u = tmp.first;
    long long v = tmp.second;
    Add_edge(key[u], key[v]);
  }
  for (long long i = 2; i <= 1e6; i++)
    if (SNT[i].size() >= 2) {
      cout << 2 << endl;
      return;
    } else if (SNT[i].size() == 1) {
      avail[1] = 1;
      avail[i] = 1;
      Add_edge(key[1], key[i]);
    }
  cout << shortest_cycle(n);
}
int main() {
  if (fopen("test"
            ".inp",
            "r")) {
    freopen(
        "test"
        ".inp",
        "r", stdin);
    freopen(
        "test"
        ".out",
        "w", stdout);
  };
  while (t--) {
    Input();
    Prepare();
    Solve();
  }
}