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:
//package Round628;

import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

/**
 * @author sguar <shugangcao@gmail.com>
 * strive for greatness
 * Created on 2020-01-10
 */
public class E {
    InputStream is;
    PrintWriter out;
    private static final String INPUT_FILE_NAME = "/Users/sguar/IdeaProjects/kotlinLearn/src/input.txt";


    private static final int N = 1_000_001;
    private static final int INF = N + 1;
    ArrayList<Integer>[] path;
    int[] dist;
    Set<Integer> primeSet = new HashSet<>();


    void solve() {
        int n = ni();
        int[] a = na(n);

        //Arrays.sort(a);
        path = new ArrayList[N];
        dist = new int[N];
        for (int i = 1; i < N; i++) {
            path[i] = new ArrayList<>();
        }

        PrimeUtil primeUtil = new PrimeUtil(N);


        debug(primeUtil.factor[10]);
        debug(primeUtil.getPrimeFactors(10));
        debug(primeUtil.getPrimeFactors(5));
        debug(primeUtil.getPrimeFactors(100001));
        for (int x : a) {
            List<Integer> primesOfAi = primeUtil.getPrimeFactors(x);

            if (primesOfAi.isEmpty()) {
                debug("1", x);
                out.println(1);
                out.flush();
                System.exit(0);
            } else if (primesOfAi.size() == 1) {
                primesOfAi.add(1);
            }

            int u = primesOfAi.get(0);
            int v = primesOfAi.get(1);
            path[u].add(v);
            path[v].add(u);

            primeSet.addAll(primesOfAi);
        }

        int result =
                primeSet.stream().filter(prime -> prime <= 1000)
                        .map(this::getCircleLength)
                        .reduce(Math::min)
                        .get();

        out.println(result >= INF ? -1 : result);
    }


    private int getCircleLength(int start) {
        int ans = INF;

        primeSet.forEach(i -> dist[i] = INF);
        dist[start] = 0;

        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            int now = queue.poll();

           // debug(now, dist[now], path[now]);
            for (int next : path[now]) {

                if (dist[next] >= dist[now]) {
                    ans = Math.min(ans, dist[next] + dist[now] + 1);
                    //debug(next, dist[next], ans);
                }

                if (dist[next] > dist[now] + 1) {
                    dist[next] = dist[now] + 1;
                    queue.add(next);
                }
            }
        }
        return ans;
    }

    class PrimeUtil {
        PrimeUtil(int primeMax) {
            init(primeMax);
        }
        int [] factor;

        void init(int primeMax) {
            factor = new int[primeMax];
            for(int i = 2; i < primeMax; i++) {
                if(factor[i] == 0) {
                    for(int j = i; j >= i && j < primeMax; j += i) {
                        if(factor[j] == 0) {
                            factor[j] = i;
                        }
                    }
                }
            }
        }

        List<Integer> getPrimeFactors(int x) {
            List<Integer> factors = new ArrayList<>();
            while (x > 1) {
                int fac = factor[x];
                int cnt = 0;

                while (x % fac == 0) {
                    x /= fac;
                    cnt++;
                }

                if (cnt % 2 == 1) {
                    factors.add(fac);
                }
            }
            return factors;
        }

    }


    class Pair {
        int x;
        int y;

        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "x: " + x + ", y: " + y;
        }

    }

    public static long invl(long a, long mod) {
        long b = mod;
        long p = 1, q = 0;
        while (b > 0) {
            long c = a / b;
            long d;
            d = a;
            a = b;
            b = d % b;
            d = p;
            p = q;
            q = d - c * q;
        }
        return p < 0 ? p + mod : p;
    }


    void run() throws Exception {

        is = oj ? System.in : new FileInputStream(INPUT_FILE_NAME);
        out = new PrintWriter(System.out);

        long s = System.currentTimeMillis();
        solve();
        out.flush();
        debug(System.currentTimeMillis() - s + "ms");
    }

    public static void main(String[] args) throws Exception {
        new E().run();
    }

    private byte[] inbuf = new byte[1024];
    int lenbuf = 0;
    int ptrbuf = 0;

    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {
                lenbuf = is.read(inbuf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];
    }

    private boolean isSpaceChar(int c) {
        return !(c >= 33 && c <= 126);
    }

    private int skip() {
        int b;
        while ((b = readByte()) != -1 && isSpaceChar(b)) ;
        return b;
    }

    private double nd() {
        return Double.parseDouble(ns());
    }

    private char nc() {
        return (char) skip();
    }

    private String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) {
            buf[p++] = (char) b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private char[][] nm(int n, int m) {
        char[][] map = new char[n][];
        for (int i = 0; i < n; i++) map[i] = ns(m);
        return map;
    }

    private int[] na(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = ni();
        return a;
    }

    private int ni() {
        int num = 0, b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }

        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }

        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

    private void debug(Object... o) {
        if (!oj) System.out.println(Arrays.deepToString(o));
    }

    private void debug(Object a, Object o) {
        if (!oj) {
            System.out.println(a.toString() + ": " + o.toString());
        }
    }
}