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.*;
import java.text.*;

public class E1325 {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		int n = sc.nextInt();
		int[] in = sc.nextIntArr(n);

		int[] arr = new int[(int) 1e6 + 1];
		for (int i = 1; i < arr.length; i++) {
			for (int j = i; j < arr.length; j += i) {
				arr[j]++;
			}
		}
		int[][] arr2 = new int[(int) 1e6 + 1][2];
		for (int i = 2; i < arr.length; i++) {
			if (arr2[i][0] == 0)
				for (int j = i; j < arr.length; j += i) {
					if (arr2[j][0] == 0) {
						arr2[j][0] = i;
					} else
						arr2[j][1] = i;
				}
		}
		ArrayList<Integer> primes = new ArrayList<Integer>();
		for (int i = 1; i < arr.length; i++) {
			if (arr[i] == 2) {
				primes.add(i);
			}
		}

		for (int i = 0; i < (int) 1e6 + 1; i++) {
			if (arr[i] > 7)
				continue;
			if (arr2[i][1] == 0) {
				if (arr[i] % 2 == 1)
					arr2[i][0] = 0;

			} else if (arr[i] == 6) {
				if (i == arr2[i][0] * arr2[i][0] * arr2[i][1]) {
					arr2[i][0] = arr2[i][1];
					arr2[i][1] = 0;
				} else
					arr2[i][1] = 0;
			}
		}

		HashSet<Integer> test = new HashSet<Integer>();
		for (int i = 0; i < in.length; i++) {
			if (arr2[in[i]][0] == 0) {
				pw.println(1);
				pw.close();
				return;
			}
			if (arr2[in[i]][1] == 0) {
				in[i] = arr2[in[i]][0];
			}
			test.add(in[i]);
		}
		if (test.size() != in.length) {
			pw.println(2);
			pw.close();
			return;
		}
		int[] hm = new int[(int) 1e6 + 1];
		for (int i = 0; i < primes.size(); i++)
			hm[primes.get(i)] = i;
		ArrayList<Integer> adjList[] = new ArrayList[primes.size() + 1];
		for (int i = 0; i < adjList.length; i++) {
			adjList[i] = new ArrayList<Integer>();
		}
		hm[1] = adjList.length - 1;
		for (int i = 0; i < n; i++) {
			int x = in[i];
			int k = arr2[x][0];
			int h = x / k;
			k = hm[k];
			h = hm[h];
			adjList[k].add(h);
			adjList[h].add(k);
		}
		int[][] adjList2 = new int[adjList.length][];
		for (int i = 0; i < adjList2.length; i++) {
			adjList2[i] = new int[adjList[i].size()];
			for (int j = 0; j < adjList2[i].length; j++) {
				adjList2[i][j] = adjList[i].get(j);
			}
		}
		adjList = null;
		int idx = 0;
		int min = (int) 1e9;
//		for (int i = 0; i < 10; i++) {
//			pw.println(adjList[i]);
//		}
//		pw.println(adjList[adjList.length - 1]);
		while (true) {
			if (primes.get(idx) * primes.get(idx) > (int) 1e6)
				break;
			int[] dist = new int[adjList2.length];
			Arrays.fill(dist, -1);
			dist[idx] = 0;
			int[] par = new int[adjList2.length];
			Arrays.fill(par, -1);
			Queue<Integer> q = new LinkedList<Integer>();
			q.add(idx);
			int f = (int) 1e9;
			while (!q.isEmpty()) {
				int cur = q.poll();
				for (int x : adjList2[cur]) {
					if (dist[x] == -1) {
						dist[x] = dist[cur] + 1;
						par[x] = cur;
						q.add(x);
					} else if (x != idx && x != par[cur]) {
						f = Math.min(dist[cur] + dist[x] + 1, f);
//						if (idx == 0)
//							pw.println(f + " " + cur + " " + x + " " + (dist[cur] + dist[x] + 1));
					}
				}
			}
			min = Math.min(min, f);
			idx++;
		}
		pw.println(min == (int) 1e9 ? -1 : min);
		pw.close();
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(FileReader r) {
			br = new BufferedReader(r);
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

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

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArr(int n) throws IOException {
			int[] arr = new int[n];
			for (int i = 0; i < arr.length; i++)
				arr[i] = nextInt();
			return arr;
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}
}