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;
struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
  };
} fast_ios_;
template <typename A, typename B>
bool chkmin(A &a, const B &b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}
template <typename A, typename B>
bool chkmax(A &a, const B &b) {
  if (b > a) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
istream &operator>>(istream &stream, vector<T> &vec) {
  for (auto &x : vec) stream >> x;
  return stream;
}
void scan() {}
template <class T, class... Args>
void scan(T &a, Args &...rest) {
  cin >> a;
  scan(rest...);
}
using ll = long long;
using vl = vector<ll>;
using vb = vector<bool>;
using vi = vector<int>;
using pii = pair<int, int>;
template <typename T>
using vv = vector<vector<T>>;
template <typename T>
ostream &operator<<(ostream &stream, const vector<T> &vec) {
  if (!vec.empty()) {
    stream << vec[0];
    for (size_t i = 1; i != vec.size(); ++i) stream << ' ' << vec[i];
  }
  return stream;
}
template <typename T>
void print(const vector<T> &t) {
  cout << t << '\n';
}
template <typename T>
void print(const vector<vector<T>> &t) {
  for (const auto &row : t) {
    print(row);
  }
}
template <typename T>
void print(const T &t) {
  cout << t << ' ';
}
template <typename T, typename... Args>
void print(const T &t, const Args &...rest) {
  print(t);
  print(rest...);
}
template <typename T>
void println(const T &t) {
  cout << t << '\n';
}
template <typename T, typename... Args>
void println(const T &t, const Args &...rest) {
  print(t);
  println(rest...);
}
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
int main() {
  int n;
  scan(n);
  vi a(n);
  scan(a);
  int ma = *max_element(begin(a), end(a));
  vi squares;
  for (int i = 2; i * i <= ma; ++i) {
    squares.push_back(i * i);
  }
  reverse(begin(squares), end(squares));
  auto normalize = [&](int x) {
    for (const auto &y : squares)
      if (x % y == 0) {
        return x / y;
      }
    return x;
  };
  for (auto &x : a) {
    x = normalize(x);
    if (x == 1) {
      println(1);
      return 0;
    }
  }
  42;
  ma = *max_element(begin(a), end(a));
  vv<pii> g(ma + 1);
  auto add_edge = [cnt = 0, &g](int u, int v) mutable {
    42;
    g[u].emplace_back(v, cnt);
    g[v].emplace_back(u, cnt);
    ++cnt;
  };
  for (const auto &x : a) {
    bool is_prime = true;
    for (int i = 2; i * i < x; ++i) {
      if (x % i == 0) {
        add_edge(i, x / i);
        is_prime = false;
        break;
      }
    }
    if (is_prime) {
      add_edge(1, x);
    }
  }
  auto bfs = [&](int s) {
    vi d(ma + 1, -1);
    vb used(n);
    d[s] = 0;
    queue<int> que;
    que.push(s);
    int ans = INT_MAX;
    while (!que.empty()) {
      int u = que.front();
      que.pop();
      for (auto [v, id] : g[u]) {
        if (v < s || used[id]) continue;
        used[id] = true;
        if (d[v] == -1) {
          d[v] = d[u] + 1;
          que.push(v);
        } else {
          chkmin(ans, d[u] + d[v] + 1);
        }
      }
    }
    return ans;
  };
  int ans = INT_MAX;
  for (int s = 1; s * s < ma; ++s) {
    if (g[s].empty()) continue;
    chkmin(ans, bfs(s));
  }
  println(ans == INT_MAX ? -1 : ans);
  return 0;
}