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 N = 1e6;
long long spf[N + 1];
void eratosthenes() {
  spf[1] = 1;
  for (long long i = 2; i <= N; i++) {
    if (spf[i] != 0) {
      continue;
    }
    spf[i] = i;
    for (long long j = i * i; j <= N; j += i) {
      if (spf[j] != 0) {
        continue;
      }
      spf[j] = i;
    }
  }
}
vector<long long> req[N + 1];
void initReq() {
  for (long long t = 2; t < N; t++) {
    long long p = spf[t];
    req[t] = req[t / p];
    auto it = find(req[t].begin(), req[t].end(), p);
    if (it == req[t].end()) {
      req[t].push_back(p);
    } else {
      req[t].erase(it);
    }
  }
}
vector<long long> adj[N + 1];
long long dist[N + 1];
void initDist() {
  for (long long i = 0; i <= N; i++) {
    dist[i] = 4000000000000000000;
  }
}
int main() {
  eratosthenes();
  initReq();
  long long t;
  cin >> t;
  long long ans = 4000000000000000000;
  while (t--) {
    long long a;
    cin >> a;
    long long g, h;
    vector<long long>::iterator it;
    switch (req[a].size()) {
      case 0:
        while (t--) cin >> a;
        cout << 1;
        return 0;
      case 1:
        g = 1;
        h = req[a][0];
        break;
      case 2:
        g = req[a][0];
        h = req[a][1];
        break;
    }
    if (find(adj[g].begin(), adj[g].end(), h) == adj[g].end()) {
      adj[g].push_back(h);
      adj[h].push_back(g);
    } else {
      ans = 2;
    }
  }
  if (ans == 2) {
    cout << 2;
    return 0;
  }
  for (long long I = 1; I <= N; I++) {
    if (I != spf[I]) {
      continue;
    }
    if (I * I > N) {
      continue;
    }
    initDist();
    queue<pair<long long, long long> > bfsQ;
    assert(bfsQ.empty());
    bfsQ.push(pair<long long, long long>(I, 0));
    dist[I] = 0;
    while (!bfsQ.empty()) {
      long long u = bfsQ.front().first;
      long long p = bfsQ.front().second;
      bfsQ.pop();
      for (long long v : adj[u]) {
        if (v == p) {
          continue;
        }
        if (dist[v] < 4000000000000000000) {
          ans = min(ans, dist[u] + dist[v] + 1);
        } else {
          bfsQ.push(pair<long long, long long>(v, u));
          dist[v] = dist[u] + 1;
        }
      }
    }
  }
  cout << (ans == 4000000000000000000 ? -1 : ans);
}