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;
const int MAXN = 1000000;
int sito[MAXN + 5];
int tab[MAXN + 5];
int skad[1000000 + 5];
vector<int> sas[MAXN + 5];
int odw[MAXN + 5];
int pr_div[100000 + 5][2];
int dist[1000000 + 5];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  for (int i = 2; i * i <= MAXN; i++)
    if (!sito[i])
      for (int j = i * 2; j <= MAXN; j += i) sito[j] = i;
  vector<int> v;
  for (int i = 1; i <= n; i++) {
    cin >> tab[i];
    v.push_back(tab[i]);
    int pier_ = sqrt(tab[i]);
    pier_ *= pier_;
    if (pier_ == tab[i]) {
      cout << 1;
      return 0;
    }
  }
  sort(v.begin(), v.end());
  for (int i = 1; i < v.size(); i++)
    if (v[i] == v[i - 1]) {
      cout << 2;
      return 0;
    }
  vector<int> vec;
  for (int i = 1; i <= n; i++) {
    if (sito[tab[i]]) {
      int ile_1 = 0, ile_2 = 0;
      int value = tab[i];
      while (value % sito[tab[i]] == 0) {
        ile_1++;
        value /= sito[tab[i]];
      }
      if (ile_1 % 2)
        pr_div[i][0] = sito[tab[i]];
      else
        pr_div[i][0] = 1;
      int dzielnik = sito[value];
      if (sito[value]) {
        while (value % dzielnik == 0) {
          ile_2++;
          value /= dzielnik;
        }
        if (ile_2 % 2)
          pr_div[i][1] = dzielnik;
        else
          pr_div[i][1] = 1;
      } else
        pr_div[i][1] = value;
    } else {
      pr_div[i][0] = tab[i];
      pr_div[i][1] = 1;
    }
  }
  for (int i = 1; i <= n; i++) vec.push_back(pr_div[i][0] * pr_div[i][1]);
  sort(vec.begin(), vec.end());
  for (int i = 1; i < vec.size(); i++)
    if (vec[i] == vec[i - 1]) {
      cout << 2;
      return 0;
    }
  int max_ = INT_MIN;
  for (int i = 1; i <= n; i++) {
    int v1 = pr_div[i][0];
    int v2 = pr_div[i][1];
    max_ = max({max_, v1 * v2});
    sas[v1].push_back(v2);
    sas[v2].push_back(v1);
  }
  int min_res = INT_MAX;
  for (int i = 1; i * i <= max_; i++)
    if (sas[i].size()) {
      queue<pair<pair<int, int>, int>> Q;
      Q.push({{i, i}, 0});
      bool b = 1;
      while (!Q.empty() && b) {
        int top_w = Q.front().first.first;
        int pop_w = Q.front().first.second;
        int top_d = Q.front().second;
        Q.pop();
        if (odw[top_w] != i) {
          skad[top_w] = pop_w;
          odw[top_w] = i;
          dist[top_w] = top_d;
          for (int j = 0; j < sas[top_w].size(); j++)
            if (sas[top_w][j] != pop_w)
              Q.push({{sas[top_w][j], top_w}, top_d + 1});
        } else {
          min_res = min(min_res, top_d + dist[top_w]);
          b = 0;
        }
      }
    }
  if (min_res == INT_MAX) {
    cout << -1;
    return 0;
  }
  cout << min_res;
}