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:
//created by Whiplash99
import java.io.*;
import java.util.*;
public class E
{
    private static final int lim=(int)(1e6+5);
    private static int[] dist, parent, spf;
    private static ArrayList<Integer> edge[], vis;

    private static void sieve()
    {
        for(int i=2;i<lim;i++)
        {
            if(spf[i]==0)
            {
                spf[i]=i;
                if((long)i*i<lim)
                    for(int j=i*i;j<lim;j+=i)
                    {
                        if(spf[j]==0)
                            spf[j]=i;
                    }
            }
        }
    }
    private static int normalise(int N)
    {
        int val=1;
        while (N>1)
        {
            int f=spf[N];
            int c=0;

            while (spf[N]==f)
            {
                c^=1;
                N/=f;
            }
            if(c==1) val*=f;
        }
        return val;
    }
    private static int cycleLength(int u)
    {
        vis.clear();
        vis.add(u);
        dist[u]=0;
        int ans=lim;

        ArrayDeque<Integer> queue=new ArrayDeque<>();
        queue.add(u);

        outer: while (!queue.isEmpty())
        {
            int v=queue.poll();
            for(int child:edge[v])
            {
                if(dist[child]==-1)
                {
                    dist[child]=dist[v]+1;
                    parent[child]=v;

                    vis.add(child);
                    queue.add(child);
                }
                else if(parent[v]!=child)
                {
                    ans=dist[v]+dist[child]+1;
                    break outer;
                }
            }
        }

        for(int i:vis) dist[i]=-1;
        return ans;
    }
    public static void main(String[] args) throws IOException
    {
        Reader r=new Reader();
        int i,N,max=0;

        vis=new ArrayList<>();
        spf=new int[lim];
        dist=new int[lim];
        parent=new int[lim];
        edge=new ArrayList[lim];
        for(i=0;i<lim;i++) edge[i]=new ArrayList<>();
        Arrays.fill(dist,-1);

        sieve();

        N=r.nextInt();
        int a[]=new int[N];
        for(i=0;i<N;i++)
            a[i]=r.nextInt();

        for(i=0;i<N;i++)
        {
            a[i]=normalise(a[i]);
            max=Math.max(a[i],max);

            if(a[i]==1)
            {
                System.out.println(1);
                System.exit(0);
            }

            int u=spf[a[i]];
            int v=a[i]/u;

            edge[u].add(v);
            edge[v].add(u);
        }

        for(i=0;i<lim;i++)
        {
            Collections.sort(edge[i]);
            for(int j=0;j<edge[i].size()-1;j++)
            {
                if(edge[i].get(j)==edge[i].get(j+1))
                {
                    System.out.println(2);
                    System.exit(0);
                }
            }
        }

        int ans=lim;
        int sqrt=(int)(Math.sqrt(max));
        
        for(i=1;i<=sqrt;i++)
        {
            if(edge[i].isEmpty()) continue;
            ans=Math.min(ans,cycleLength(i));
        }

        System.out.println(ans==lim?-1:ans);
    }
    static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;private DataInputStream din;private byte[] buffer;private int bufferPointer, bytesRead;
        public Reader(){din=new DataInputStream(System.in);buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;
        }public Reader(String file_name) throws IOException{din=new DataInputStream(new FileInputStream(file_name));buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;
    }public String readLine() throws IOException{byte[] buf=new byte[64];int cnt=0,c;while((c=read())!=-1){if(c=='\n')break;buf[cnt++]=(byte)c;}return new String(buf,0,cnt);
    }public int nextInt() throws IOException{int ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;
    }public long nextLong() throws IOException{long ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;
    }public double nextDouble() throws IOException{double ret=0,div=1;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c = read();do {ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(c=='.')while((c=read())>='0'&&c<='9')ret+=(c-'0')/(div*=10);if(neg)return -ret;return ret;
    }private void fillBuffer() throws IOException{bytesRead=din.read(buffer,bufferPointer=0,BUFFER_SIZE);if(bytesRead==-1)buffer[0]=-1;
    }private byte read() throws IOException{if(bufferPointer==bytesRead)fillBuffer();return buffer[bufferPointer++];
    }public void close() throws IOException{if(din==null) return;din.close();}
    }
}