1325_E. Ehab's REAL Number Theory 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.
```python
from collections import deque
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())

```