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 lld = long long int;
using pii = pair<int, int>;
int n;
vector<int> a[100009];
int pa[1000009];
int p[1000009];
int pl;
int spl;
void inil() {
  int i, j, k;
  for (i = 2; i <= 1000000; i++) {
    if (pa[i] == 0) {
      pa[i] = pl;
      p[pl++] = i;
      for (j = i; j <= 1000000 / i; j++) {
        pa[i * j] = 1;
      }
    }
    if (i == 1000) {
      spl = pl;
    }
  }
}
vector<int> v[100009];
bool self[100009];
int ind[100009];
int mask[100009];
int pp[100009];
int hh[100009];
int ss[100009];
int tt[100009];
int res;
int findp(int x) {
  if (x == pp[x]) return x;
  return pp[x] = findp(pp[x]);
}
void combine(int i, int j) {
  int ii = findp(i);
  int jj = findp(j);
  if (ii == jj) return;
  if (hh[ii] > hh[jj]) {
    pp[jj] = ii;
    ss[ii] += ss[jj];
    tt[ii] += tt[jj];
  } else if (hh[ii] < hh[jj]) {
    pp[ii] = jj;
    ss[jj] += ss[ii];
    tt[jj] += tt[ii];
  } else {
    pp[ii] = jj;
    ss[jj] += ss[ii];
    tt[jj] += tt[ii];
    hh[jj]++;
  }
}
int sv[100009];
vector<int> svv[100009];
int svl;
int ssvl;
void dfs(int si) {
  mask[si] = 1;
  sv[svl++] = si;
  for (int i = 0; i < v[si].size(); i++) {
    int j = v[si][i];
    if (mask[j] == 0) {
      dfs(j);
    }
  }
}
int df[209][209];
int dd[100009];
int dp[100009];
int smask[209];
int bmask[209];
void process(int si) {
  svl = 0;
  dfs(si);
  sort(sv, sv + svl);
  for (ssvl = 0; ssvl < svl; ssvl++) {
    if (sv[ssvl] >= spl) break;
  }
  int i, j, k;
  for (i = 0; i < svl; i++) {
    svv[i].clear();
    int vti = sv[i];
    for (j = 0; j < v[vti].size(); j++) {
      k = v[vti][j];
      int ki = lower_bound(sv, sv + svl, k) - sv;
      svv[i].push_back(ki);
    }
  }
  for (i = 0; i < ssvl; i++) {
    for (j = 0; j < svl; j++) {
      dd[j] = -1;
      dp[j] = -1;
    }
    dd[i] = 0;
    dp[i] = -1;
    priority_queue<pii> tq;
    tq.push(pii(0, i));
    while (!tq.empty()) {
      pii tt = tq.top();
      tq.pop();
      int tm = -tt.first;
      int ti = tt.second;
      if (dd[ti] < tm) continue;
      for (j = 0; j < svv[ti].size(); j++) {
        k = svv[ti][j];
        if (dd[k] == -1 || dd[k] > dd[ti] + 1) {
          dd[k] = dd[ti] + 1;
          dp[k] = ti;
          tq.push(pii(-dd[k], k));
        } else if (dd[k] >= 0) {
          if (dp[ti] != k) {
            int cur = dd[k] + dd[ti] + 1;
            if (res == -1 || res > cur) {
              res = cur;
            }
          }
        }
      }
    }
    for (j = 0; j < ssvl; j++) {
      df[i][j] = dd[j];
    }
  }
  set<int> loopzero;
  set<int> loopone;
  for (i = 0; i < ssvl; i++) {
    int vti = sv[i];
    if (self[vti]) {
      loopzero.insert(i);
    }
    smask[i] = 0;
    bmask[i] = -1;
  }
  for (i = ssvl; i < svl; i++) {
    int vti = sv[i];
    if (self[vti]) {
      for (j = 0; j < svv[i].size(); j++) {
        int ki = svv[i][j];
        if (ki < ssvl) {
          if (smask[ki] == 0) {
            loopone.insert(ki);
            smask[ki] = 1;
            bmask[ki] = i;
          } else {
            bmask[ki] = -1;
            if (res == -1 || res > 4) res = 4;
          }
        }
      }
    }
  }
  for (auto it : loopzero) {
    for (auto jt : loopzero) {
      if (it == jt) continue;
      int cur = df[it][jt] + 2;
      if (res == -1 || res > cur) res = cur;
    }
    for (auto jt : loopone) {
      int cur = df[it][jt] + 3;
      if (res == -1 || res > cur) res = cur;
    }
  }
  for (auto it : loopone) {
    for (auto jt : loopone) {
      if (it == jt) continue;
      if (bmask[it] >= 0 && bmask[jt] >= 0 && bmask[it] == bmask[jt]) continue;
      int cur = df[it][jt] + 4;
      if (res == -1 || res > cur) res = cur;
    }
  }
}
int main() {
  inil();
  int i, j, k;
  int t = 1, tv = 0;
  while (t--) {
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
      scanf("%d", &k);
      for (j = 0; j < pl && p[j] <= k / p[j]; j++) {
        if (k % p[j] == 0) {
          int cur = 0;
          while (k % p[j] == 0) {
            k /= p[j];
            cur ^= 1;
          }
          if (cur) {
            a[i].push_back(j);
          }
        }
      }
      if (k > 1) {
        a[i].push_back(pa[k]);
      }
    }
    sort(a, a + n, [](const vector<int>& p, const vector<int>& q) {
      for (int i = 0; i < p.size() && i < q.size(); i++) {
        if (p[i] - q[i]) return p[i] < q[i];
      }
      return p.size() < q.size();
    });
    if (a[0].size() == 0) {
      printf("1\n");
      continue;
    }
    for (i = 0; i < n - 1; i++) {
      if (a[i] == a[i + 1]) {
        printf("2\n");
        break;
      }
    }
    if (i < n - 1) continue;
    for (i = 0; i < pl; i++) {
      pp[i] = i;
      hh[i] = 0;
      ss[i] = 1;
      tt[i] = 0;
      mask[i] = 0;
    }
    for (i = 0; i < n; i++) {
      if (a[i].size() == 1) {
        self[a[i][0]] = true;
        tt[findp(a[i][0])]++;
      } else {
        v[a[i][0]].push_back(a[i][1]);
        v[a[i][1]].push_back(a[i][0]);
        ind[a[i][0]]++;
        ind[a[i][1]]++;
        combine(a[i][0], a[i][1]);
        tt[findp(a[i][0])]++;
      }
    }
    res = -1;
    for (i = 0; i < pl; i++) {
      if (i == findp(i)) {
        if (ss[i] > 1 && ss[i] <= tt[i]) {
          process(i);
        }
      }
    }
    printf("%d\n", res);
  }
}