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:
//stan hu tao
//join nct ridin by first year culture reps
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import java.util.*;
import java.io.*;
import java.math.*;

public class x1325E
{
    static final int MAX = 1000000;
    public static void main(String hi[]) throws Exception
    {
        int[] factor = new int[MAX+1];
        Arrays.fill(factor, 1);
        for(int d=2; d <= MAX; d++)
            for(int v=d; v <= MAX; v+=d)
                if(factor[v] == 1)
                    factor[v] = d;
        FastScanner infile = new FastScanner();
        int N = infile.nextInt();
        boolean[] exists = new boolean[MAX+1];
        boolean dupe = false;
        for(int i=0; i < N; i++)
        {
            int x = infile.nextInt();
            if(x > 1)
            {
                int val = 1;
                int a = factor[x];
                int tag = 0;
                while(x%a == 0)
                {
                    x /= a;
                    tag ^= 1;
                }
                if(tag == 1)
                    val = a;
                if(x > 1)
                {
                    a = factor[x];
                    tag = 0;
                    while(x%a == 0)
                    {
                        x /= a;
                        tag ^= 1;
                    }
                    if(tag == 1)
                        val *= a;
                }
                x = val;
            }
            if(exists[x])
                dupe = true;
            exists[x] = true;
        }
        if(exists[1])
        {
            System.out.println(1);
            return;
        }
        if(dupe)
        {
            System.out.println(2);
            return;
        }
        int[] freq = new int[MAX+1];
        for(int v=2; v <= MAX; v++)
            if(exists[v])
            {
                int a = factor[v];
                int b = v/factor[v];
                freq[a]++;
                freq[b]++;
            }
        int[][] edges = new int[MAX+1][];
        for(int i=0; i <= MAX; i++)
            edges[i] = new int[freq[i]];
        for(int v=2; v <= MAX; v++)
            if(exists[v])
            {
                int a = factor[v];
                int b = v/factor[v];
                edges[a][--freq[a]] = b;
                edges[b][--freq[b]] = a;
                if(debug)System.out.println(a+" "+b);
            }
        int res = Integer.MAX_VALUE;
        int[] visited = new int[MAX+1];
        int[] dist = new int[MAX+1];
        int[] par = new int[MAX+1];
        int time = 1;
        for(int v=1; v <= 1000; v++)
            if(edges[v].length > 0)
            {
                ArrayDeque<Integer> q = new ArrayDeque<Integer>();
                q.add(v);   visited[v] = time;
                dist[v] = 0;
                while(q.size() > 0)
                {
                    int curr = q.poll();
                    //if(debug&&v==2)System.out.println(curr+" "+dist[curr]);
                    for(int next: edges[curr])
                    {
                        if(visited[next] < time)
                        {
                            visited[next] = time;
                            dist[next] = dist[curr]+1;
                            par[next] = curr;
                            q.add(next);
                        }
                        else if(par[curr] != next && par[next] != curr)
                            res = min(res, dist[curr]+dist[next]+1);
                    }
                }
                time++;
            }
        if(res == Integer.MAX_VALUE)
            res = -1;
        System.out.println(res);
    }
    static boolean debug = false;
}
class FastScanner
{
    private int BS = 1 << 16;
    private char NC = (char) 0;
    private byte[] buf = new byte[BS];
    private int bId = 0, size = 0;
    private char c = NC;
    private double cnt = 1;
    private BufferedInputStream in;

    public FastScanner() {
        in = new BufferedInputStream(System.in, BS);
    }

    public FastScanner(String s) {
        try {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        } catch (Exception e) {
            in = new BufferedInputStream(System.in, BS);
        }
    }

    private char getChar() {
        while (bId == size) {
            try {
                size = in.read(buf);
            } catch (Exception e) {
                return NC;
            }
            if (size == -1) return NC;
            bId = 0;
        }
        return (char) buf[bId++];
    }

    public int nextInt() {
        return (int) nextLong();
    }

    public int[] nextInts(int N) {
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            res[i] = (int) nextLong();
        }
        return res;
    }

    public long[] nextLongs(int N) {
        long[] res = new long[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextLong();
        }
        return res;
    }

    public long nextLong() {
        cnt = 1;
        boolean neg = false;
        if (c == NC) c = getChar();
        for (; (c < '0' || c > '9'); c = getChar()) {
            if (c == '-') neg = true;
        }
        long res = 0;
        for (; c >= '0' && c <= '9'; c = getChar()) {
            res = (res << 3) + (res << 1) + c - '0';
            cnt *= 10;
        }
        return neg ? -res : res;
    }

    public double nextDouble() {
        double cur = nextLong();
        return c != '.' ? cur : cur + nextLong() / cnt;
    }

    public double[] nextDoubles(int N) {
        double[] res = new double[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextDouble();
        }
        return res;
    }

    public String next() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c > 32) {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public String nextLine() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c != '\n') {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public boolean hasNext() {
        if (c > 32) return true;
        while (true) {
            c = getChar();
            if (c == NC) return false;
            else if (c > 32) return true;
        }
    }
}