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.*;
import java.util.*;
 
public class GFG {
    private static int MAX=1000000000;
	private static int factor(int a){
		int n=1,cnt=0;
		while(a%2==0){
			a/=2;
			cnt++;
		}
		if(cnt%2!=0)
			n=2;
		for(int i=3;i*i<=a;i+=2){
			cnt=0;
			while(a%i==0){
				a/=i;
				cnt++;
			}
			if(cnt%2!=0)
				n*=i;
		}
		if(a!=1)
			n*=a;
		return n;
	}
	private static void find(int a,Map<Integer,ArrayList<Integer>> map,int[] prime){
		ArrayList<Integer> A=new ArrayList<>();
		for(int i=2;i*i<=a;i++){
			if(a%i==0){
				A.add(i);
				A.add(a/i);
				prime[i]=1;
				prime[a/i]=1;
				map.put(a,A);
				return;
			}
		}
		A.add(a);
		A.add(1);
		prime[a]=1;
		map.put(a,A);
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//int t = Integer.parseInt(br.readLine().trim());
		//while (t-- != 0) {
			int n = Integer.parseInt(br.readLine().trim());			
			String s = br.readLine().trim();
			String ss[]=s.split("\\s+");
			int a[]=new int[n];
			for(int i=0;i<n;i++)
				a[i]=Integer.parseInt(ss[i]);
			HashSet<Integer> set=new HashSet<>();
			for(int i:a)
				set.add(factor(i));
			if(set.contains(1)){
				System.out.println("1");
				return;
			}
			if(set.size()!=n){
				System.out.println("2");
				return;
			}
			int prime[]=new int[1000000];
			Map<Integer,ArrayList<Integer>> map=new HashMap<>();
			for(int i:set)
				find(i,map,prime);
			int j=0;
			int pi[]=new int[1000000];
			ArrayList<Integer> P=new ArrayList<>();
			pi[1]=j++;
			P.add(1);
			for(int i=2;i<pi.length;i++){
				if(prime[i]!=0){
					pi[i]=j++;
					P.add(i);
				}
			}
			ArrayList<Integer> G[]=new ArrayList[j];
			for(int i=0;i<j;i++)
				G[i]=new ArrayList<>();			
			for(int i:set){
				ArrayList<Integer> A=map.get(i);
				int u=pi[A.get(0)];
				int v=pi[A.get(1)];
			//	System.out.println(i+"="+u+" "+v);
				G[u].add(v);
				G[v].add(u);
			}
			int ans=MAX;
			for(int i=0;i<j;i++){
				if(P.get(i)*P.get(i)>1000000)
					break;
				int d[]=new int[j];
				Arrays.fill(d,MAX);
				d[i]=0;
				int p[]=new int[j];
				Queue<Integer> q=new LinkedList<>();
				q.add(i);
				while(!q.isEmpty()){
					int u=q.poll();
					for(int k=0;k<G[u].size();k++){
						int v=G[u].get(k);
						if(d[v]==MAX){
							d[v]=d[u]+1;
							p[v]=u;
							q.add(v);
						}
						else if(p[v]!=u&&p[u]!=v)
							ans=Math.min(ans,d[u]+d[v]+1);
					}
				}				
			}
			
			System.out.println((ans==MAX)?-1:ans);
		//}
	}
}