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 \le n \le 10^5$) — the length of $a$.

The second line contains $n$ integers $a_1$, $a_2$, $\ldots$, $a_{n}$ ($1 \le a_i \le 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.

Difficulty: MEDIUM

Starter code:

Solutions:
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
Primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997)
E = [[] for i in range(10 ** 6)]
U = set()
for i in range(n):
	a = A[i]
	X = []
	for p in Primes:
		while a % (p * p) == 0:
			a //= p * p
		if a % p == 0:
			a //= p
			X.append(p)
	if a != 1:
		X.append(a)
	if a == 1 and X == []:
		print(1)
		sys.exit()
	elif len(X) == 1:
		E[1].append(X[0])
		E[X[0]].append(1)
		U.add(X[0])
	else:
		E[X[0]].append(X[1])
		E[X[1]].append(X[0])
		U.add(X[0] * X[1])
if len(A) != len(U):
	ANS = 2
else:
	ANS = n + 5
D = []
E2 = []
for i in range(10 ** 6):
	if E[i] == []:
		continue
	D.append(i)
	E2.append(E[i])
DD = {x: i for (i, x) in enumerate(D)}
for i in range(len(E2)):
	for k in range(len(E2[i])):
		E2[i][k] = DD[E2[i][k]]
from collections import deque
for start in range(min(170, len(E2))):
	if E2[start] == []:
		continue
	Q = deque([start])
	D = [0] * len(E2)
	FROM = [0] * len(E2)
	D[start] = 1
	while Q:
		x = Q.popleft()
		if D[x] * 2 - 2 >= ANS:
			break
		for to in E2[x]:
			if to == FROM[x]:
				continue
			elif D[to] == 0:
				Q.append(to)
				FROM[to] = x
				D[to] = D[x] + 1
			else:
				ANS = min(ANS, D[x] + D[to] - 1)
if ANS > len(A):
	print(-1)
else:
	print(ANS)


import sys
MAX = 1000005
lp = [0] * MAX
pr = []
pid = {1: 0}
for i in range(2, MAX):
	if not lp[i]:
		lp[i] = i
		pr.append(i)
		pid[i] = len(pr)
	for p in pr:
		if p > lp[i] or i * p >= MAX:
			break
		lp[i * p] = p
n = int(input())
a = list(map(int, input().split()))
g = [[] for _ in range(len(pid))]
e = set()
for x in a:
	f = []
	while x > 1:
		(p, c) = (lp[x], 0)
		while lp[x] == p:
			x //= p
			c ^= 1
		if c:
			f.append(p)
	if not f:
		print(1)
		return
	f += [1] * (2 - len(f))
	(u, v) = (pid[f[0]], pid[f[1]])
	if (u, v) in e or (v, u) in e:
		print(2)
		return
	g[u].append(v)
	g[v].append(u)

def bfs(s):
	d = [-1] * len(pid)
	d[s] = 0
	q = [(s, -1)]
	while q:
		q2 = []
		for (u, p) in q:
			for v in g[u]:
				if d[v] != -1:
					if v != p:
						return d[u] + d[v] + 1
				else:
					d[v] = d[u] + 1
					q2.append((v, u))
		q = q2
ans = n + 1
for i in range(len(pid)):
	if i > 0 and pr[i - 1] ** 2 >= MAX:
		break
	ans = min(ans, bfs(i) or ans)
print(ans if ans <= n else -1)


from collections import deque, defaultdict
import sys
input = sys.stdin.readline

def make_mf():
	res = [-1] * (mxa + 5)
	ptoi = [0] * (mxa + 5)
	pn = 1
	for i in range(2, mxa + 5):
		if res[i] == -1:
			res[i] = i
			ptoi[i] = pn
			pn += 1
			for j in range(i ** 2, mxa + 5, i):
				if res[j] == -1:
					res[j] = i
	return (res, ptoi, pn)

def make_to():
	to = [[] for _ in range(pn)]
	ss = set()
	for a in aa:
		pp = []
		while a > 1:
			p = mf[a]
			e = 0
			while p == mf[a]:
				a //= p
				e ^= 1
			if e:
				pp.append(p)
		if len(pp) == 0:
			ext(1)
		elif len(pp) == 1:
			pp.append(1)
		(u, v) = (ptoi[pp[0]], ptoi[pp[1]])
		to[u].append(v)
		to[v].append(u)
		if pp[0] ** 2 <= mxa:
			ss.add(u)
		if pp[1] ** 2 <= mxa:
			ss.add(v)
	return (to, ss)

def ext(ans):
	print(ans)
	exit()

def solve():
	ans = inf
	for u in ss:
		ans = bfs(u, ans)
	if ans == inf:
		ans = -1
	return ans

def bfs(u, ans):
	dist = [-1] * pn
	q = deque()
	q.append((u, 0, -1))
	dist[u] = 0
	while q:
		(u, d, pu) = q.popleft()
		if d * 2 >= ans:
			break
		for v in to[u]:
			if v == pu:
				continue
			if dist[v] != -1:
				ans = min(ans, d + dist[v] + 1)
			dist[v] = d + 1
			q.append((v, d + 1, u))
	return ans
inf = 10 ** 9
n = int(input())
aa = list(map(int, input().split()))
mxa = max(aa)
(mf, ptoi, pn) = make_mf()
(to, ss) = make_to()
print(solve())