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 __future__ import division, print_function
import bisect
import math
import itertools
import sys
from atexit import register
 
if sys.version_info[0] < 3:
    from io import BytesIO as stream
else:
    from io import StringIO as stream
 
 
if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)
 
        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)
 
        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)
 
    input = raw_input
    range = xrange
 
    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip
 
 
def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.
 
    Args:
        sync (bool, optional): The new synchronization setting.
 
    """
    global input, flush
 
    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')
 
        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))
 
def main():
    from collections import deque
 
    def bfs(graph, root, prune_level):
        """make a pruned BFS search of the graph starting at root.
        returns the BFS tree, and possibly a traversal edge (u,v) that with the tree
        forms a cycle of some length.
        Complexity: O(V + E)
        """
        n = len(graph)
        level = [-1] * n                      # -1 == not seen
        tree = [None] * n                     # pointers to predecessors
        toVisit = deque([root])               # queue for BFS
        level[root] = 0
        tree[root] = root
        best_cycle = float('inf')             # start with infinity
        best_u = None
        best_v = None
        while toVisit:
            u = toVisit.popleft()
            if level[u] > prune_level:
                break
            for v in graph[u]:
                if tree[u] == v:              # ignore the tree edge
                    continue
                if level[v] == -1:            # new vertex - tree edge
                    level[v] = level[u] + 1
                    toVisit.append(v)
                    tree[v] = u
                else:                         # vertex already seen - traversal edge
                    prune_level = level[v] - 1
                    cycle_len = level[u] + 1 + level[v]
                    if cycle_len < best_cycle:  # footnote (1)
                        best_cycle = cycle_len
                        best_u = u
                        best_v = v
        return tree, best_cycle, best_u, best_v
     
     
    def path(tree, v):
        """returns the path in the tree from v to the root
        Complexity: O(V)
        """
        P = []
        while not P or P[-1] != v:
            P.append(v)
            v = tree[v]
        return P
     
     
    def shortest_cycle(graph):
        """Returns a shortest cycle if there is any
        Complexity: O(V * (V + E))
        """
        best_cycle = float('inf')
        best_u = None
        best_v = None
        best_tree = None
        V = list(range(len(graph)))
        for root in V:
            tree, cycle_len, u, v = bfs(graph, root, best_cycle // 2)
            if cycle_len < best_cycle:
                best_cycle = cycle_len
                best_u = u
                best_v = v
                best_tree = tree
        if best_cycle == float('inf'):
            return []                   # no cycle found
        Pu = path(best_tree, best_u)
        Pv = path(best_tree, best_v)
        return Pu[::-1] + Pv
    n=int(input()) 
    jj=list(map(int, input().split()))
    c=0
    p=[]
    a=[]
    for i in jj:
        if i!=0:
            a.append(i)
    n=len(a)
    def dtb(n,b):  
      
        if(n > 1):  
            dtb(n//2,b)  
      
          
        b.append(n%2) 
    cnt=[0]*70    
    for i in range(n):
        b=[]
        dtb(a[i],b)
        l=-1
        for j in range(len(b)-1,-1,-1):
            l+=1
            if b[j]==1:
                cnt[l]+=1
                if cnt[l]>2:
                    print('3')
                    exit()
                p.append([l,a[i]])
    p.sort()
    g=[set() for x in range(n)]
    a.sort()
    #aprint(a,p)
    for i in range(len(p)-1):
        if p[i][0]==p[i+1][0]:
            k=bisect.bisect_left(a,p[i][1])
            j=i+1
            lp=len(p)
            while(p[i][0]==p[j][0] and j<lp):
                t=bisect.bisect_left(a,p[j][1])
                g[k].add(t)
                g[t].add(k)
                j+=1
                if (j== lp):
                    break
    #print(g)            
    print(len(shortest_cycle(g)) - 1)       
if __name__ == '__main__':
    sync_with_stdio(False)
    main()