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;
mt19937 rnd(228);
const int N = 1e6 + 10, INF = 1e9 + 10;
int d[N];
void precalc() {
  for (int i = 2; i < N; ++i) {
    if (!d[i]) {
      d[i] = i;
      for (int j = i; j < N; j += i) {
        d[j] = i;
      }
    }
  }
}
vector<int> factorization(int x) {
  vector<int> res;
  while (x != 1) {
    res.push_back(d[x]);
    x /= d[x];
  }
  return res;
}
vector<int> g[N];
bool used[N];
int cnt[N], h[N], ans = INF, dist[N], pr[N];
map<pair<int, int>, int> lol;
void dfs(int v, int p = -1) {
  used[v] = true;
  for (auto to : g[v]) {
    if (to == p) {
      continue;
    }
    if (used[to]) {
      if (h[to] != INF) {
        ans = min(ans, abs(h[to] - h[v]) + 1);
      }
    } else {
      h[to] = h[v] + 1;
      dfs(to, v);
    }
  }
}
void bfs() {
  fill(used, used + N, false);
  queue<int> q;
  for (int i = 0; i < N; ++i) {
    if (cnt[i]) {
      pr[i] = i;
      dist[i] = 0;
      used[i] = true;
      q.push(i);
    }
  }
  while ((int)(q).size() > 0) {
    int v = q.front();
    q.pop();
    for (auto to : g[v]) {
      if (!used[to]) {
        dist[to] = dist[v] + 1;
        used[to] = true;
        pr[to] = pr[v];
        q.push(to);
      }
    }
  }
  for (int i = 2; i < N; ++i) {
    if (used[i]) {
      for (auto to : g[i]) {
        if (used[to] && pr[to] != pr[i]) {
          ans = min(ans, dist[i] + dist[to] + 3);
        }
      }
    }
  }
}
void solve() {
  srand(time(0));
  precalc();
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    if (x == 1) {
      cout << 1;
      exit(0);
    }
    vector<int> primes = factorization(x);
    sort((primes).begin(), (primes).end());
    if (primes[0] == primes.back()) {
      if ((int)(primes).size() & 1) {
        ++cnt[primes[0]];
      } else {
        cout << 1;
        exit(0);
      }
    } else {
      int p1 = primes[0], p2 = primes.back();
      int cnt1 = 0, cnt2 = 0;
      for (auto x : primes) {
        if (x == p1) {
          cnt1 ^= 1;
        } else {
          cnt2 ^= 1;
        }
        assert(x == p2 || x == p1);
      }
      if (cnt1 && cnt2) {
        g[p1].push_back(p2);
        g[p2].push_back(p1);
        ++lol[make_pair(p1, p2)];
        ++lol[make_pair(p2, p1)];
        continue;
      }
      if (!cnt1 && !cnt2) {
        cout << 1;
        exit(0);
      }
      if (cnt1) {
        ++cnt[p1];
      }
      if (cnt2) {
        ++cnt[p2];
      }
    }
  }
  for (auto x : lol) {
    if (x.second >= 2) {
      cout << 2;
      exit(0);
    }
  }
  for (int i = 2; i < N; ++i) {
    if (cnt[i] >= 2) {
      cout << 2;
      exit(0);
    }
  }
  bfs();
  vector<int> kek;
  for (int i = 2; i < N; ++i) {
    if ((int)(g[i]).size() > 0) {
      kek.push_back(i);
    }
  }
  int W = 1000;
  if ((int)(kek).size() > W * 3) {
    while (clock() < 2950) {
      random_shuffle((kek).begin(), (kek).end());
      for (int i = 0; i < W; ++i) {
        used[kek[i]] = true;
        h[kek[i]] = INF;
      }
      for (int i = W; i < (int)(kek).size(); ++i) {
        used[kek[i]] = false;
        h[kek[i]] = 0;
        random_shuffle((g[kek[i]]).begin(), (g[kek[i]]).end());
      }
      for (auto v : kek) {
        if (!used[v]) {
          dfs(v);
        }
      }
    }
  } else {
    while (clock() < 2950) {
      for (auto v : kek) {
        used[v] = false;
        h[v] = 0;
        random_shuffle((g[v]).begin(), (g[v]).end());
      }
      for (auto v : kek) {
        if (!used[v]) {
          dfs(v);
        }
      }
    }
  }
  cout << (ans == INF ? -1 : ans);
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout.precision(12);
  solve();
  return 0;
}