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 JAVA):

Solution:
import java.util.*;
import java.io.*;

public class CFA {
  BufferedReader br;
  PrintWriter out;
  StringTokenizer st;
  boolean eof;
  private static final long MOD = 1000L * 1000L * 1000L + 7;
  private static final int[] dx = {0, -1, 0, 1};
  private static final int[] dy = {1, 0, -1, 0};
  private static final String yes = "Yes";
  private static final String no = "No";

  void solve() {
//    int T = nextInt();
    int T = 1;
    for (int i = 0; i < T; i++) {
      helper();
    }
  }

  List<List<Integer>> graph;
  void helper() {
    int n = nextInt();
    int[] arr = nextIntArr(n);
    int LIMIT = 1000 * 1000 + 10;
    int[] prev = new int[LIMIT];
    int[] id = new int[LIMIT];
    int[] back = new int[LIMIT];
    Arrays.fill(prev, -1);
    int sz = 1;
    for (int i = 2; i < LIMIT; i++) {
      if (prev[i] == -1) {
        id[i] = sz;
        back[sz] = i;
        sz++;
        for (int j = i; j < LIMIT; j += i) {
          prev[j] = i;
        }
      }
    }

    graph = new ArrayList<>();
    for (int i = 0; i < sz + 5; i++) {
      graph.add(new ArrayList<>());
    }
    for (int v : arr) {
      int N = v;
      List<Integer> res = new ArrayList<>();
      while (N > 1) {
        int cnt = 0;
        int f = prev[N];
        while (N % f == 0) {
          cnt++;
          N = N / f;
        }
        if (cnt % 2 == 1) {
          res.add(f);
        }
      }

      if (res.isEmpty()) {
        outln(1);
        return;
      } else {
        int f1 = res.get(0);
        int f2 = 1;
        if (res.size() > 1) {
          f2 = res.get(1);
        }
        graph.get(id[f1]).add(id[f2]);
        graph.get(id[f2]).add(id[f1]);
      }
    }
    for (List<Integer> ls : graph) {
      Set<Integer> uniq = new HashSet<>(ls);
      if (uniq.size() != ls.size()) {
        outln(2);
        return;
      }
    }
    int[] distance = new int[LIMIT];
    int[] firstPar = new int[LIMIT];
    int res = Integer.MAX_VALUE;
    for (int a = 0; back[a] < 1005 && a <= sz; a++) {
      // Find the shortest cycle in the component of i.
      for (int i = 0; i <= sz; i++) {
        distance[i] = -1;
        firstPar[i] = i;
      }

      Deque<Integer> deck = new LinkedList<>();
      distance[a] = 0;
      firstPar[a] = -1;
      deck.push(a);
      while (!deck.isEmpty()) {
        int v = deck.pollFirst();
        for (int u : graph.get(v)) {
          if (distance[u] == -1) {
            distance[u] = distance[v] + 1;
            if (firstPar[v] != -1) firstPar[u] = firstPar[v];
            deck.push(u);
          }
          else if (firstPar[u] != firstPar[v] && firstPar[u] != -1 && firstPar[v] != -1) {
            res = Math.min(res, distance[u] + distance[v] + 1);
          }
        }
      }
    }

    outln(res == Integer.MAX_VALUE ? -1 : res);
  }

  void shuffle(long[] a) {
    int n = a.length;
    for(int i = 0; i < n; i++) {
      int r = i + (int) (Math.random() * (n - i));
      long tmp = a[i];
      a[i] = a[r];
      a[r] = tmp;
    }
  }

  long gcd(long a, long b) {
    while(a != 0 && b != 0) {
      long c = b;
      b = a % b;
      a = c;
    }
    return a + b;
  }
  private void outln(Object o) {
    out.println(o);
  }
  private void out(Object o) {
    out.print(o);
  }
  private void formatPrint(double val) {
    outln(String.format("%.9f%n", val));
  }
  public CFA() {
    br = new BufferedReader(new InputStreamReader(System.in));
    out = new PrintWriter(System.out);
    solve();
    out.close();
  }
  public static void main(String[] args) {
    new CFA();
  }

  public long[] nextLongArr(int n) {
    long[] res = new long[n];
    for(int i = 0; i < n; i++)
      res[i] = nextLong();
    return res;
  }
  public int[] nextIntArr(int n) {
    int[] res = new int[n];
    for(int i = 0; i < n; i++)
      res[i] = nextInt();
    return res;
  }
  public String nextToken() {
    while (st == null || !st.hasMoreTokens()) {
      try {
        st = new StringTokenizer(br.readLine());
      } catch (Exception e) {
        eof = true;
        return null;
      }
    }
    return st.nextToken();
  }
  public String nextString() {
    try {
      return br.readLine();
    } catch (IOException e) {
      eof = true;
      return null;
    }
  }
  public int nextInt() {
    return Integer.parseInt(nextToken());
  }
  public long nextLong() {
    return Long.parseLong(nextToken());
  }
  public double nextDouble() {
    return Double.parseDouble(nextToken());
  }
}