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: interview

Starter code:

Solutions:
MAX = 1_000_005
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))]
ec = 0
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)
        import sys
        return
    f += [1] * (2 - len(f))
    u, v = pid[f[0]], pid[f[1]]
    g[u].append((v, ec))
    g[v].append((u, ec))
    ec += 1

def bfs(p):
    d = [-1] * len(pid)
    d[p] = 0
    q = [(p, -1)]
    while q:
        q2 = []
        for u, peid in q:
            for v, eid in g[u]:
                if d[v] != -1:
                    if eid != peid:
                        return d[u] + d[v] + 1
                else:
                    d[v] = d[u] + 1
                    q2.append((v, eid))
        q = q2

ans = -1
for i in range(len(pid)):
    if i > 0 and pr[i - 1] ** 2 >= MAX:
        break
    cyc = bfs(i) or ans
    if ans == -1 or cyc < ans:
        ans = cyc
print(ans)

import sys

MAX = 1_000_005
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)


import sys

MAX = 1_000_005
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)