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.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.Reader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class C1325E_1 {

    static final int NO_ANSWER = (int) 1e9;
    private static boolean debug = false;

    public static void main(String[] args) throws IOException {

//        {
//            long t = System.nanoTime();
//            var limit = (int) 1e6;
//            var oneFactor = new int[limit + 1];
//            var primeFactorCounts = new int[limit + 1];
//            var factors = new ArrayList<List<Integer>>(limit + 1);
//            factors.add(List.of());
//            factors.add(List.of(1));
//            var ans = new int[limit + 1][2];
////            var ans = new int[2][limit + 1];
////            var ans = new int[s2 * limit];
//            System.out.println((System.nanoTime() - t) / 1e9);
//        }
//        {
//            long t = System.nanoTime();
//            int[] a = new int[(int) 1e6];
//            System.out.println((System.nanoTime() - t) / 1e9);
//            t = System.nanoTime();
//            Arrays.fill(a, -1);
//            System.out.println((System.nanoTime() - t) / 1e9);
//        }
//        {
//            long t = System.nanoTime();
//            int[][] ints = new int[(int) 1e6 + 1][];
//            System.out.println((System.nanoTime() - t) / 1e9);
//        }

        var scanner = new BufferedScanner();
        var writer = new BufferedWriter(new PrintWriter(System.out));

        var t = System.nanoTime();
//        var primes0 = primes((long) 1e6);
//        debug("primes 1e12: " + (System.nanoTime() - t) / 1e9);
//        t = System.nanoTime();
        var n = scanner.nextInt();
//        debug = n == 80106; // == 35965;// || n == 78500;
//        var n = 35965;
        var a = new int[n];
//        var aa = new ArrayList<Integer>();
//        for (int i = 0; i < primes0.size(); i++) {
//            aa.add(primes0.get(i));
//            for (int j = i + 1; j < primes0.size(); j++) {
//                aa.add(primes0.get(i) * primes0.get(j));
//            }
//        }
//        var a = aa.stream().mapToInt(i -> i).toArray();
//        var n = a.length;
//        debug("n: " + n);
        var maxA = -1;
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
//            a[i] = randomA(primes0, (int) 1e6);
            maxA = Math.max(maxA, a[i]);
        }
        debug("maxA: " + maxA);
//        debug("random1: " + random1count);
//        debug("random2: " + random2count);
        t = System.nanoTime();
        var factors = factors((int) 1e6);
        debug("factors: " + (System.nanoTime() - t) / 1e9);
//        debug("maxA: " + maxA);
//        debug("randomA: " + (System.nanoTime() - t) / 1e9);
//        t = System.nanoTime();
//        var primes = primes(maxA);
//        debug("primes: " + (System.nanoTime() - t) / 1e9);
        t = System.nanoTime();
        var connect = new HashMap<Integer, Set<Integer>>();
        var ans = NO_ANSWER;
        for (int x : a) {
            var fs = factors.get(x);
            if (fs.size() == 0) {
                ans = 1;
                break;
            }
            int p, q;
            if (fs.size() == 1) {
                p = 1;
                q = fs.get(0);
            } else {
                p = fs.get(0);
                q = fs.get(1);
            }
            if (put(connect, p, q) || put(connect, q, p)) {
                ans = 2;
            }
        }
        debug("connect: " + (System.nanoTime() - t) / 1e9);
        debug("connect size: " + connect.size());

        if (ans == NO_ANSWER) {
            var nodes = connect.keySet().stream()
                    .filter(k -> connect.get(k).size() > 1)
                    .sorted()
                    .collect(Collectors.toList());
            var connect2 = new HashMap<Integer, List<Integer>>();
            var connect3 = new HashMap<Integer, int[]>();
            for (Map.Entry<Integer, Set<Integer>> entry : connect.entrySet()) {
                connect2.put(entry.getKey(), List.copyOf(entry.getValue()));
                connect3.put(entry.getKey(), entry.getValue().stream().mapToInt(i -> i).toArray());
            }
            var dist = new int[maxA + 1];
            var from = new int[maxA + 1];
            for (int start : nodes) {
                if (start <= maxA / start) {
                    t = System.nanoTime();
                    init(dist, from, connect.keySet());
                    ans = Math.min(ans, bfs(start, connect2, connect3, dist, from, ans));
                    if (bfsCount0 > 160) {
                        debug("bfs " + bfsCount0 + " for " + start + " done for " + (System.nanoTime() - t) / 1e9);
                    }
                }
            }
//            debug("bfs: " + (System.nanoTime() - t) / 1e9);
            debug("bfsCount: " + bfsCount);
            debug("bfsCount0: " + bfsCount0);
        }

        ans = ans < NO_ANSWER ? ans : -1;
        writer.write(String.valueOf(ans));

        scanner.close();
        writer.flush();
        writer.close();
    }

    private static void init(int[] dist, int[] from, Set<Integer> nodes) {
        for (Integer node : nodes) {
            dist[node] = 0;
            from[node] = 0;
        }
    }

    private static void debug(String s) {
        if (debug) {
            System.out.println(s);
        }
    }

    private static List<List<Integer>> factors(int limit) {
        var oneFactor = new int[limit + 1];
        var factors = new ArrayList<List<Integer>>(limit + 1);
        factors.add(List.of());
        factors.add(List.of());
        var t1 = 0;
        var t2 = 0;
        for (int i = 2; i <= limit; i++) {
            if (oneFactor[i] == 0) {
                var t = System.nanoTime();
                oneFactor[i] = i;
                factors.add(List.of(i));
                int multiple = i + i;
                while (multiple <= limit) {
                    oneFactor[multiple] = i;
                    multiple += i;
                }
                t2 += System.nanoTime() - t;
            } else {
                var t = System.nanoTime();
                var subFactors = factors.get(i / oneFactor[i]);
                var thisFactors = new ArrayList<>(subFactors);
                if (thisFactors.contains(oneFactor[i])) {
                    thisFactors.remove(Integer.valueOf(oneFactor[i]));
                } else {
                    thisFactors.add(oneFactor[i]);
                }
                factors.add(thisFactors);
                t1 += System.nanoTime() - t;
            }
        }
//        debug("t1: " + t1 / 1e9);
//        debug("t2: " + t2 / 1e9);
        return factors;
    }

    static int random1count = 0;
    static int random2count = 0;

    private static int randomA(List<Integer> primes, int limit) {
        var a = primes.get((int) (Math.random() * primes.size()));
        var b = primes.get((int) (Math.random() * primes.size()));
        if ((long) a * b > limit) {
            random1count++;
            return a;
        } else {
            random2count++;
            return a * b;
        }
    }

    private static boolean put(Map<Integer, Set<Integer>> connect, int a, int b) {
        Set<Integer> cs = connect.get(a);
        if (cs != null && cs.contains(b)) {
            return true;
        }
        connect.putIfAbsent(a, new HashSet<>());
        connect.get(a).add(b);
        return false;
    }

    static int bfsCount0 = 0;
    static int bfsCount = 0;

    private static int bfs(int start, Map<Integer, List<Integer>> connect,
            Map<Integer, int[]> connect3, int[] dist, int[] from, int ans) {
        var q = new LinkedList<Integer>();
//        var dist = new HashMap<Integer, Integer>();
//        var from = new HashMap<Integer, Integer>();
        bfsCount0++;
        q.add(start);
//        dist.put(start, 0);
//        from.put(start, start);
        from[start] = start;
        while (!q.isEmpty()) {
            bfsCount++;
            var h = q.poll();
            var d0 = dist[h];
            if (2 * d0 >= ans) {
                break;
            }
            var hFrom = from[h];
//            for (int next : connect.get(h)) {
            var nextList = connect3.get(h);
            for (int next : nextList) {
//                var d1 = dist.get(next);
                if (from[next] == 0) {
                    q.add(next);
//                    dist.put(next, d0 + 1);
//                    from.put(next, h);
                    dist[next] = d0 + 1;
                    from[next] = h;
                } else if (next != hFrom) {
                    var d = d0 + 1 + dist[next];
                    ans = Math.min(ans, d);
                }
            }
        }
//        debug("bfs " + bfsCount0 + " done");
        return ans;
    }

    private static List<Integer> primes(long upperBound) {
        var limit = (int) Math.sqrt(upperBound);
        var isComposite = new boolean[limit + 1];
        var primes = new ArrayList<Integer>();
        for (int i = 2; i <= limit; i++) {
            if (isComposite[i]) {
                continue;
            }
            primes.add(i);
            int j = i + i;
            while (j <= limit) {
                isComposite[j] = true;
                j += i;
            }
        }
        return primes;
    }

    public static class BufferedScanner {
        BufferedReader br;
        StringTokenizer st;

        public BufferedScanner(Reader reader) {
            br = new BufferedReader(reader);
        }

        public BufferedScanner() {
            this(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        void close() {
            try {
                br.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }

    static long gcd(long a, long b) {
        if (a < b) {
            return gcd(b, a);
        }
        while (b > 0) {
            long tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }

    static long inverse(long a, long m) {
        long[] ans = extgcd(a, m);
        return ans[0] == 1 ? (ans[1] + m) % m : -1;
    }

    private static long[] extgcd(long a, long m) {
        if (m == 0) {
            return new long[]{a, 1, 0};
        } else {
            long[] ans = extgcd(m, a % m);
            long tmp = ans[1];
            ans[1] = ans[2];
            ans[2] = tmp;
            ans[2] -= ans[1] * (a / m);
            return ans;
        }
    }

}