You are given n integer numbers a_1, a_2, ..., a_n. Consider graph on n nodes, in which nodes i, j (i≠ j) are connected if and only if, a_i AND a_j≠ 0, where AND denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND).

Find the length of the shortest cycle in this graph or determine that it doesn't have cycles at all.

Input

The first line contains one integer n (1 ≤ n ≤ 10^5) — number of numbers.

The second line contains n integer numbers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^{18}).

Output

If the graph doesn't have any cycles, output -1. Else output the length of the shortest cycle.

Examples

Input


4
3 6 28 9


Output


4

Input


5
5 12 9 16 48


Output


3

Input


4
1 2 4 8


Output


-1

Note

In the first example, the shortest cycle is (9, 3, 6, 28).

In the second example, the shortest cycle is (5, 12, 9).

The graph has no cycles in the third example.

def naiveSolve(n):
    
    
    
    return

from collections import deque

def main():
    
    n=int(input())
    a=readIntArr()
    
    idxWithSetBit=[[] for _ in range(60)]
    for i,x in enumerate(a):
        for j in range(60):
            if (x&(1<<j))>0:
                idxWithSetBit[j].append(i)
                if len(idxWithSetBit[j])==3:
                    print(3)
                    return
                
    
    # at most 60 edges, 1 per bit
    edges=set()
    for listt in idxWithSetBit:
        if len(listt)==2:
            u,v=listt
            if v<u:
                temp=v
                v=u
                u=temp
            edges.add((u,v))
    edges=list(edges)
    m=len(edges)
    ans=inf
    for skip in range(m):
        u,v=edges[skip]
        adj=[[] for _ in range(n)]
        for i in range(m):
            if i==skip:
                continue
            uu,vv=edges[i]
            adj[uu].append(vv)
            adj[vv].append(uu)
        visited=[False]*n
        visited[u]=True
        # bfs from u to v
        q=deque() # [node,dist]
        q.append([u,0])
        while q:
            node,dist=q.popleft()
            if node==v:
                ans=min(ans,dist+1)
                break
            for nex in adj[node]:
                if visited[nex]==False:
                    visited[nex]=True
                    q.append([nex,dist+1])
    if ans==inf:
        ans=-1
    print(ans)
    
    return


import sys
# input=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)
input=lambda: sys.stdin.readline().rstrip("\r\n") #FOR READING STRING/TEXT INPUTS.

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
 
def readIntArr():
    return [int(x) for x in input().split()]
# def readFloatArr():
#     return [float(x) for x in input().split()]
 
def makeArr(defaultValFactory,dimensionArr): # eg. makeArr(lambda:0,[n,m])
    dv=defaultValFactory;da=dimensionArr
    if len(da)==1:return [dv() for _ in range(da[0])]
    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
 
def queryInteractive(i,j):
    print('? {} {}'.format(i,j))
    sys.stdout.flush()
    return int(input())
 
def answerInteractive(ans):
    print('! {}'.format(' '.join([str(x) for x in ans])))
    sys.stdout.flush()
 
inf=float('inf')
MOD=10**9+7
# MOD=998244353

from math import gcd,floor,ceil
 
for _abc in range(1):
    main()
