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;
template <typename T>
void UpdateMax(T& a, T b) {
  if (a < b) a = b;
}
template <typename T>
void UpdateMin(T& a, T b) {
  if (a > b) a = b;
}
template <typename T>
inline void read(T& x) {
  x = 0;
  char c = getchar();
  int flag = 1;
  while (!isdigit(c)) {
    if (c == '-') flag = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= flag;
}
template <typename T>
void Unique(vector<T>& vec) {
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
}
template <typename T>
void Relabel(vector<T>& vec, T& value) {
  value = lower_bound(vec.begin(), vec.end(), value) - vec.begin() + 1;
}
template <typename T, typename V>
void Print(const pair<T, V>& x) {
  cout << x.first << " @ " << x.second << " | ";
}
template <typename T>
void Print(const T& x) {
  cout << x << " ";
}
template <typename T>
void Pcon(const T& x) {
  cout << "\nsize: " << x.size() << endl;
  for (const auto& item : x) Print(item);
}
std::vector<int> LABS;
template <typename T>
void Print(const T* x, int offset, int loop) {
  for (int i = 0; i <= loop; i++) {
    cout << "[";
    for (int item : LABS) cout << item - offset << ",";
    cout << i - offset << "]:";
    cout << x[i] << " ";
  }
}
template <typename T, typename... Args>
void Print(const T* f, int offset, int loop, Args... args) {
  for (int i = 0; i <= loop; i++) {
    LABS.push_back(i);
    Print(f[i], offset, args...);
    cout << endl;
    LABS.pop_back();
  }
}
clock_t start_time;
inline void SetClock() { start_time = clock(); }
bool TimeOut(size_t ms) {
  if (1000 * (clock() - start_time) >= ms * ((clock_t)1000)) return true;
  return false;
}
const long long MOD = 1e12 + 7;
const int N = 1e6 + 5;
int ans, n, times;
int vis[N], dis[N], vis_edg[N], q[N];
vector<int> G[N], edgs;
void solve(int x) {
  ++times;
  int s = 0, t = 1;
  q[s] = x;
  dis[x] = 0;
  vis[x] = times;
  while (s != t) {
    int u = q[s];
    for (int item : G[u]) {
      if (vis_edg[item] == times) continue;
      vis_edg[item] = times;
      int v = edgs[item] ^ u;
      if (vis[v] == times) {
        UpdateMin(ans, dis[v] + 1 + dis[u]);
      } else {
        vis[v] = times;
        dis[v] = dis[u] + 1;
        q[t] = v;
        t++;
      }
    }
    s++;
  }
}
int main() {
  srand(time(0));
  SetClock();
  cin.sync_with_stdio(false);
  ans = 2000000000ll;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    long long x;
    cin >> x;
    unordered_map<int, int> factor;
    for (long long j = 2; j * j <= x; j++) {
      while (x % j == 0) {
        ++factor[j];
        x /= j;
      }
    }
    if (x != 1) {
      ++factor[x];
    }
    vector<int> factors;
    for (const auto& item : factor) {
      if (item.second & 1) {
        factors.push_back(item.first);
      }
    }
    if (factors.size() == 1) {
      G[1].push_back(edgs.size());
      G[factors[0]].push_back(edgs.size());
      edgs.push_back(1 ^ factors[0]);
    } else if (factors.size() == 2) {
      G[factors[0]].push_back(edgs.size());
      G[factors[1]].push_back(edgs.size());
      edgs.push_back(factors[0] ^ factors[1]);
    } else {
      cout << 1 << endl;
      return 0;
    }
  }
  for (int i = 1; i <= 1000; i++) {
    solve(i);
  }
  if (ans != 2000000000ll)
    cout << ans << endl;
  else
    cout << -1 << endl;
}