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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.Queue;
import java.util.ArrayDeque;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        HashMap<Integer, Integer> map = new HashMap<>();
        HashMap<Integer, Integer> rev = new HashMap<>();
        HashSet<Integer> seen = new HashSet<>();
        boolean two = false;
        ArrayList<Edge>[] graph;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int cnt = 1;
            int N = in.nextInt();
            int[][] edge = new int[N][2];
            for (int i = 0; i < N; i++) {
                int a = in.nextInt();
                ArrayList<Integer> div = new ArrayList<>();
                for (int d = 2; d <= Math.sqrt(a); d++) {
                    if (a % d == 0) {
                        int tot = 0;
                        while (a % d == 0) {
                            tot++;
                            a /= d;
                        }
                        if (tot % 2 == 1) {
                            if (!map.containsKey(d)) {
                                map.put(d, cnt++);
                                rev.put(cnt - 1, d);
                            }
                            div.add(d);
                        }
                    }
                }
                if (a > 1) {
                    div.add(a);
                    if (!map.containsKey(a)) {
                        map.put(a, cnt++);
                        rev.put(cnt - 1, a);
                    }
                }
                if (div.size() == 0) {
                    out.println(1);
                    return;
                }
                if (seen.contains(prod(div))) {
                    two = true;
                } else {
                    seen.add(prod(div));
                }
                if (div.size() > 1) {
                    edge[i] = new int[]{map.get(div.get(0)), map.get(div.get(1))};
                } else {
                    edge[i] = new int[]{0, map.get(div.get(0))};
                }
            }
            rev.put(0, 1);
            if (two) {
                out.println(2);
                return;
            }
            graph = new ArrayList[cnt];
            for (int i = 0; i < cnt; i++) {
                graph[i] = new ArrayList<>();
            }
            for (int i = 0; i < N; i++) {
                graph[edge[i][0]].add(new Edge(edge[i][1], i));
                graph[edge[i][1]].add(new Edge(edge[i][0], i));
            }
            out.println(shortest_cycle(cnt));
        }

        int prod(ArrayList<Integer> div) {
            if (div.size() == 1) {
                return div.get(0);
            }
            return div.get(0) * div.get(1);
        }

        int shortest_cycle(int n) {

            // To store length of the shortest cycle
            int ans = Integer.MAX_VALUE;

            // For all vertices
            for (int i = 0; i < n; i++) {
                if (rev.get(i) <= 1000) {

                    // Make distance maximum
                    int[] dist = new int[n];
                    Arrays.fill(dist, (int) 1e9);

                    // Take a imaginary parent
                    int[] par = new int[n];
                    Arrays.fill(par, -1);

                    // Distance of source to source is 0
                    dist[i] = 0;
                    Queue<Integer> q = new ArrayDeque<>();

                    // Push the source element
                    q.add(i);

                    // Continue until queue is not empty
                    while (!q.isEmpty()) {

                        // Take the first element
                        int x = q.poll();

                        // Traverse for all it's childs
                        for (Edge c : graph[x]) {
                            int child = c.a;
                            // If it is not visited yet
                            if (dist[child] == (int) (1e9)) {

                                // Increase distance by 1
                                dist[child] = 1 + dist[x];

                                // Change parent
                                par[child] = x;

                                // Push into the queue
                                q.add(child);
                            } else if (par[x] != child && par[child] != x)
                                ans = Math.min(ans, dist[x] + dist[child] + 1);
                        }
                    }
                }
            }

            // If graph contains no cycle
            if (ans == Integer.MAX_VALUE)
                return -1;

                // If graph contains cycle
            else
                return ans;
        }

        class Edge {
            int i;
            int a;

            Edge(int a, int i) {
                this.i = i;
                this.a = a;
            }

        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

    }
}