1205_B. Shortest Cycle
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.
```python
from collections import *
import sys  

# "". join(strings)  
    
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 need 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

ans = 10**5

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

    # Make distance maximum 
    dist = [int(1e5)] * n 

    # Take a imaginary parent 
    par = [-1] * n 

    # Distance of source to source is 0 
    dist[i] = 0
    q = deque() 

    # Push the source element 
    q.append(i) 

    # Continue until queue is not empty 
    while q: 

        # Take the first element 
        x = q[0] 
        q.popleft() 

        # Traverse for all it's childs 
        for child in graph[x]: 

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

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

                # Change parent 
                par[child] = x 

                # Push into the queue 
                q.append(child) 

            # If it is already visited 
            elif par[x] != child and par[child] != x: 
                ans = min(ans, dist[x] + 
                               dist[child] + 1) 



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





```