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.

# CODE BEGINS HERE.................
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())
b = list(map(int, input().split()))
a = []
for i in b:
    if i != 0:
        a.append(i)

n = len(a)

if(n > 200):
    print(3)
else:
    graph = [[] for i in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if a[i] & a[j]:
                graph[i].append(j)
                graph[j].append(i)

    # print(graph)
    print(len(shortest_cycle(graph)) - 1)


# CODE ENDS HERE....................

