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;
using pii = pair<int, int>;
const int MOD = 1000000007;
const int INF = 2000000000;
const long long DESPACITO = 1000000000000000000;
namespace minmax {
template <class T>
T max(T&& A) {
  return A;
}
template <class T>
T min(T&& A) {
  return A;
}
template <class T>
T max(T&& A, T&& B) {
  return A > B ? A : B;
}
template <class T>
T chmin2(T&& A, T&& B) {
  return A < B ? A : B;
}
template <class T, class... Ts>
T max(T&& A, Ts&&... ts) {
  T B = max(ts...);
  return A > B ? A : B;
}
template <class T, class... Ts>
T min(T&& A, Ts&&... ts) {
  T B = min(ts...);
  return A < B ? A : B;
}
template <class T, class... Ts>
T chmax(T&& A, Ts&&... ts) {
  A = max(A, ts...);
  return A;
}
template <class T, class... Ts>
T chmin(T&& A, Ts&&... ts) {
  A = min(A, ts...);
  return A;
}
template <class T1, class T2>
void chmin2(T1&& A, T2&& Aa, T1&& B, T2&& Bb) {
  if (B < A) A = B, Aa = Bb;
}
template <class T1, class T2>
void chmax2(T1&& A, T2&& Aa, T1&& B, T2&& Bb) {
  if (B > A) A = B, Aa = Bb;
}
}  // namespace minmax
namespace input {
template <class T>
void re(T&& Xx) {
  cin >> Xx;
}
template <class T1, class T2>
void re(pair<T1, T2>& Pp) {
  re(Pp.first);
  re(Pp.second);
}
template <class T>
void re(vector<T>& Aa) {
  for (int i = 0; i < (int)(Aa).size(); i++) re(Aa[i]);
}
template <class T1, class T2>
void rea(T1&& Aa, T2 t) {
  for (int i = 0; i < t; i++) re(Aa[i]);
}
template <class T1, class T2, class... Ts>
void rea(T1&& Aa, T2 t, Ts&&... ts) {
  rea(Aa, t);
  rea(ts...);
}
template <class T1, class T2>
void rea1(T1&& Aa, T2 t) {
  for (int i = 1; i <= t; i++) re(Aa[i]);
}
template <class T1, class T2, class... Ts>
void rea1(T1&& Aa, T2 t, Ts&... ts) {
  rea1(Aa, t);
  rea1(ts...);
}
template <class T, class... Ts>
void re(T&& t, Ts&... ts) {
  re(t);
  re(ts...);
}
}  // namespace input
namespace output {
void pr(int32_t Xx) { cout << Xx; }
void pr(bool Xx) { cout << Xx; }
void pr(long long Xx) { cout << Xx; }
void pr(long long unsigned Xx) { cout << Xx; }
void pr(double Xx) { cout << Xx; }
void pr(char Xx) { cout << Xx; }
void pr(const string& Xx) { cout << Xx; }
void pr(const char* Xx) { cout << Xx; }
void pr(const char* Xx, size_t len) { cout << string(Xx, len); }
void ps() { cout << "\n"; }
void pn() {}
void pw() { pr(" "); }
void pc() {
  pr("]");
  ps();
}
template <class T1, class T2>
void pr(const pair<T1, T2>& Xx) {
  pr(Xx.first);
  pw();
  pr(Xx.second);
}
template <class T>
void pr(const T&);
bool parse(const char* t) {
  if (t == "\n") return true;
  return false;
}
template <class T>
bool parse(T&& t) {
  return false;
}
template <class T1, class T2>
bool parsepair(const pair<T1, T2>& Xx) {
  return true;
}
template <class T>
bool parsepair(T&& t) {
  return false;
}
template <class T1, class T2>
void psa(T1&& Aa, T2 t) {
  for (int i = 0; i < t; i++) pr(Aa[i]), pw();
  ps();
}
template <class T1, class T2>
void pna(T1&& Aa, T2 t) {
  for (int i = 0; i < t; i++) pr(Aa[i]), ps();
}
template <class T1, class T2>
void psa2(T1&& Aa, T2 t1, T2 t2) {
  for (int i = 0; i < t1; i++) {
    for (int j = 0; j < t2; j++) pr(Aa[i][j]), pw();
    ps();
  }
}
template <class T>
void pr(const T& Xx) {
  if (!(int)(Xx).size()) return;
  bool fst = 1;
  bool op = 0;
  if (parsepair(*Xx.begin())) op = 1;
  for (const auto& Aa : Xx) {
    if (!fst) pw();
    if (op) pr("{");
    pr(Aa), fst = 0;
    if (op) pr("}");
  }
}
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) {
    if (!parse(t)) pw();
  }
  ps(ts...);
}
template <class T>
void pn(const T& t) {
  for (const auto& Aa : t) ps(Aa);
}
template <class T, class... Ts>
void pw(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pw();
  pw(ts...);
}
template <class T, class... Ts>
void pc(const T& t, const Ts&... ts) {
  bool op = 0;
  if (parsepair(t)) op = 1;
  if (op) pr("{");
  pr(t);
  if (op) pr("}");
  if (sizeof...(ts)) pr(", ");
  pc(ts...);
}
namespace trace {
template <class T1, class T2>
void __f(const char* name, const T1& Xx, const T2& y) {
  pr("[", y, "] = ");
  ps(Xx);
}
template <class T1, class T2, class... Ts>
void __f(const char* name, const T1& Xx, const T2& y, const Ts&... rest) {
  const char* open = strchr(name, '[');
  pr("[", y, "]");
  __f(open + 1, Xx, rest...);
}
template <class T1, class T2, class... Ts>
void __f0(const char* name, const T1& Xx, const T2& y, const Ts&... rest) {
  const char* open = strchr(name, '[');
  pr(name, size_t(open - name));
  __f(name, Xx, y, rest...);
}
template <class T>
void __fn(int n, const char* name, const T& Xx) {
  for (int i = 0; i < n; i++) pr(name), __f(name, Xx[i], i);
}
}  // namespace trace
}  // namespace output
using namespace minmax;
using namespace input;
using namespace output;
using namespace output::trace;
const int N = 1e6 + 5;
const int M = 1e3 + 5;
int d[N], p[N], ans = INF;
vector<int> primes, g[N];
vector<bool> prime;
void bfs(int root) {
  queue<int> q;
  vector<int> used;
  q.push(root);
  d[root] = 0;
  while (!q.empty()) {
    auto cur = q.front();
    q.pop();
    used.emplace_back(cur);
    bool skip = 1;
    for (auto nxt : g[cur]) {
      if (d[nxt] < 0) {
        d[nxt] = d[cur] + 1;
        p[nxt] = cur;
        q.push(nxt);
      } else if (p[cur] == nxt and skip)
        skip = 0;
      else
        chmin(ans, d[cur] + d[nxt] + 1);
    }
  }
  for (auto& x : used) d[x] = -1, p[x] = -1;
}
void sieve(int maxn) {
  int i, j;
  prime.assign(maxn + 1, true);
  primes.emplace_back(1);
  primes.emplace_back(2);
  prime[0] = prime[1] = false;
  for (i = 2; i <= maxn; i += 2) prime[i] = i == 2;
  for (i = 3; i * i <= maxn; i += 2)
    if (prime[i])
      for (j = i * i; j <= maxn; j += i * 2)
        if (prime[j]) prime[j] = false;
  for (i = 3; i <= maxn; i += 2)
    if (prime[i]) primes.emplace_back(i);
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int i, j, k, n;
  re(n);
  sieve(M);
  for (i = 0; i < n; i++) {
    int a;
    re(a);
    vector<int> push_front;
    for (j = 2; j * j <= a; j++) {
      int cnt = 0;
      while (a % j == 0) cnt++, a /= j;
      if (cnt & 1) push_front.emplace_back(j);
    }
    if (a > 1) push_front.emplace_back(a);
    if (!(int)(push_front).size())
      return ps(1), 0;
    else if ((int)(push_front).size() == 1) {
      g[1].emplace_back(push_front[0]);
      g[push_front[0]].emplace_back(1);
    } else if ((int)(push_front).size() == 2) {
      g[push_front[0]].emplace_back(push_front[1]);
      g[push_front[1]].emplace_back(push_front[0]);
    } else
      assert(false);
  }
  memset(d, -1, sizeof(d));
  memset(p, -1, sizeof(p));
  for (auto& x : primes) bfs(x);
  ps(ans == INF ? -1 : ans);
  return 0;
}