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.util.*;
import java.io.*;
public class E {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int n = sc.nextInt();
		HashSet<Integer> set = new HashSet<>();
		boolean two = false;
		for(int i = 0; i < n; i++) {
			int a = reduce(sc.nextInt());
			if(a == 1) {
				System.out.println(1); return;
			}
			if(set.contains(a)) {
				two = true;
			}
			set.add(a);
		}
		if(two) {
			System.out.println(2); return;
		}
		//all numbers are reduces and distinct now, that means no double edges
		HashMap<Integer, Integer> ps = new HashMap<>();
		int count = 0;
		ArrayList<Pair> pairs = new ArrayList<>();
		for(int x: set) {
			ArrayList<Integer> divs = new ArrayList<>();
			for(int d = 2; d*d <= x; d++) {
				if(x % d == 0) {
					divs.add(d);
					if(!ps.containsKey(d)) {
						ps.put(d, count++);
					}
					x /= d;
				}
			}
			if(x >= 1) {
				if(!ps.containsKey(x)) {
					ps.put(x, count++);
				}
				divs.add(x);
			}
			if(divs.size() == 1) {
				divs.add(1);
				if(!ps.containsKey(1)) {
					ps.put(1, count++);
				}
			}
			pairs.add(new Pair(divs.get(0), divs.get(1))); 
		}
		int p = count;
		int[] primes = new int[p];
		for(int prime: ps.keySet()) {
			primes[ps.get(prime)] = prime;
		}
		ArrayList<Integer>[] g = new ArrayList[p];
		for(int i = 0; i < p; i++) {
			g[i] = new ArrayList<>();
		}
		for(Pair pr: pairs) {
			g[ps.get(pr.a)].add(ps.get(pr.b));
			g[ps.get(pr.b)].add(ps.get(pr.a));
		}
		//find cycle
		int min = p+1;
		for(int u0 = 0; u0 < p; u0++) {
			if(primes[u0] <= 1000) { //
				min = Math.min(min, shortestCycle(g, p, u0));
			}
		}
		if(min > p) {
			System.out.println(-1);
		}
		else {
			System.out.println(min);
		}
	}
	static int shortestCycle(ArrayList<Integer>[] g, int n, int u0) {
		int[] p = new int[n];
		int[] dist = new int[n];
		Arrays.fill(p, -1);
		Arrays.fill(dist, -1);
		LinkedList<Integer> q = new LinkedList<>();
		q.add(u0);
		dist[u0] = 0;
		while(!q.isEmpty()) {
			int u = q.removeFirst();
			for(int v: g[u]) {
				if(dist[v] >= 0 && p[u] != v) {
					return dist[u] + dist[v] + 1;
				}
				if(dist[v] < 0) {
					p[v] = u;
					dist[v] = dist[u]+1;
					q.add(v);
				}
			}
		}
		return n+1;
	}
	static class Pair{
		int a, b;
		public Pair(int a, int b) {
			this.a = a; this.b = b;
		}
	}
	static boolean isPrime(int x) {
		for(int d = 2; d*d <= x; d++) {
			if(x % d == 0) return false;
		}
		return true;
	}
	static int reduce(int x) {
		for(int d = 2; d*d <= x; d++) {
			if(x % d == 0) {
				while(x % (d*d) == 0) x /= (d*d);
			}
		}
		return x;
	}
	static class FastScanner {
		public BufferedReader reader;
		public StringTokenizer tokenizer;
		public FastScanner() {
			reader = new BufferedReader(new InputStreamReader(System.in), 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());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch(IOException e) {
				throw new RuntimeException(e);
			}
		}
	}

}