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.
from collections import *
import sys  
  
def ri():
    return int(input())
 
def rl():
    return list(map(int, input().split()))
    

n = ri()
aa = rl()

zero_cnt = 0
aa = [value for value in aa if value != 0]
        
n = len(aa)

edges = set()
graph = defaultdict(list)
bit_shared = defaultdict(list)

#2^60 > 10^18 >= aa[i]. So we have 60 bits to check, between 0 and 59.
#Also note that for a given bit, if 3 numbers share it, then the answer is 3
for k in range(60):
    for i in range(n):
        if (1 << k) & aa[i]:
            bit_shared[k].append(i)
            if len(bit_shared[k]) >= 3:
                print(3)
                sys.exit()
# print("bit: ", bit_shared)

#we build the graph
for i in range(n):
    for j in range(i + 1, n):
        if aa[i] & aa[j]:
            if (i,j) not in edges:
                graph[i].append(j)
                graph[j].append(i)
                edges.add((i,j)) # we use a set, because sometimes many edges between same 2 vertices, but they dont count as cycle according to:
            #ANNOUCEMENT : Note that the graph does not contain parallel edges. Therefore, one edge can not be a cycle. A cycle should contain at least three distinct vertices. 

# print("graph: ",graph)
# print("edges: ",edges)

#if we havent exited yet, it means for all bit 2^k, it is shared at most between two elements of aa.

#We have to find the shortest length cycle of this graph. 

#I think we can chose to iterate over edges (there are less than 60 of them)
#Or we can iterate over vertices (there are less of 60*3 + 1 = 183 of them because of pigeonhole principle)

#let's iterate of vertices v and use BFS  to find the shortest cycle containing v
###########################################################################################################
####Approach: For every vertex, we check if it is possible to get the shortest cycle involving this vertex. 
#### we fix a vertex "source". and we maintain a queue of vertex we will check (classic BFS)
#### we also maintain for all vertices the "parent" that precedeed him in the algo
#### everytime we check a vertex in the queue, we go to its chilren.
#### if its children already had another "parent" in the algo, it means we already got there from another way ie: we have a cycle 
###########################################################################################################


ans = 10**5

# For all vertices 
for i in range(n): 

    # dist stores the distance to i. Make distance maximum 
    dist = [int(1e5)] * n 

    # except distance from i to i is 0 
    dist[i] = 0

    # At the beginning, no parents
    par = [-1] * n 

    #make a queue with just the source element
    q = deque([i]) 

    # Continue until queue is not empty 
    while q: 

        # Take the first element 
        parent = q.popleft() 

        # Traverse for all it's children
        for child in graph[parent]: 

            # If it is not visited yet 
            if dist[child] == int(1e5): 

                # Increase distance by 1 
                dist[child] = 1 + dist[parent] 

                # Change parent 
                par[child] = parent 

                # Push into the queue 
                q.append(child) 

            # If it is already visited AND there is another parent: there is a cycle 
            elif par[parent] != child and par[child] != parent: 
                ans = min(ans, dist[parent] + 
                               dist[child] + 1) 

#########################################################################################################

if ans == 10**5:
    print(-1)
else:
    print(ans)




