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.
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 *
 * @author LENOVO
 */
public class Main {

    public static int dfs(int currNode, int[][] matrix, int[] level, int currLevel, int parent) {

        level[currNode] = currLevel;

        int minCycle = Integer.MAX_VALUE;

        ArrayList<Integer> cycles = new ArrayList<Integer>();

        for (int i = 0; i < matrix.length; i++) {

            if (matrix[currNode][i] == 1) {

                if (level[i] == 0) {

                    minCycle = Math.min(minCycle, dfs(i, matrix, level, currLevel + 1, currNode));

                } else {

                    if (currLevel > level[i] && i != parent) {

                        cycles.add(level[i]);

                        int cycle = currLevel - level[i] + 1;

                        minCycle = Math.min(minCycle, cycle);

                    }

                }
            }

        }

        for (int i = 0; i < cycles.size() - 1; i++) {
            for (int j = i + 1; j < cycles.size(); j++) {

                int cycle = Math.abs(cycles.get(i) - cycles.get(j)) + 2;

                minCycle = Math.min(minCycle, cycle);

            }
        }

        return minCycle;
    }

    public static int bfs(int src, int dst, ArrayList<Integer>[] graph) {

        int n = graph.length;

        int[] minPath = new int[n];

        for (int i = 0; i < n; i++) {
            minPath[i] = 20000;
        }

        minPath[src] = 0;

        boolean[] visited = new boolean[n];

        Queue<Integer> queue = new LinkedList<Integer>();

        visited[src] = true;

        queue.add(src);

        while (!queue.isEmpty()) {
            
            int curr = queue.remove();

            for (int i = 0; i < graph[curr].size(); i++) {

                if (!visited[graph[curr].get(i)]) {
                    visited[graph[curr].get(i)] = true;
                    minPath[graph[curr].get(i)] = minPath[curr] + 1;

                    if (graph[curr].get(i) == dst) {
                        return minPath[dst];
                    }

                    queue.add(graph[curr].get(i));
                }

            }

        }

        return 20000;
    }

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        ArrayList<Long> arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            long num = in.nextLong();
            if (num != 0) {
                arr.add(num);
            }
        }

        if (arr.size() > 128) {
            System.out.println(3);
        } else {

            int nNodes = arr.size();

            ArrayList<Integer>[] graph = new ArrayList[nNodes];

            for (int i = 0; i < nNodes; i++) {

                graph[i] = new ArrayList<Integer>();

            }

            for (int i = 0; i < nNodes - 1; i++) {

                for (int j = i + 1; j < nNodes; j++) {

                    if ((arr.get(i) & arr.get(j)) != 0) {
    
                        graph[i].add(j);
                        graph[j].add(i);

                    }
                    
                    
                }
            }

            int[][] matrix = new int[nNodes][nNodes];

            for (int i = 0; i < nNodes - 1; i++) {
                for (int j = i + 1; j < nNodes; j++) {
                    if ((arr.get(i) & arr.get(j)) != 0) {
                        matrix[i][j] = 1;
                        matrix[j][i] = 1;
                    }
                }
            }
            int ans = 20000;

            for (int i = 0; i < nNodes - 1; i++) {

                for (int j = i + 1; j < nNodes; j++) {

                    if (matrix[i][j] == 1) {

                        graph[i].remove(new Integer(j));
                        graph[j].remove(new Integer(i));

                        //
                        int path = bfs(i, j, graph);

                        

                        graph[i].add(j);
                        graph[j].add(i);
                        
                        
                        ans = Math.min(ans, path + 1);

                    }

                }

            }
            System.out.println(ans == 20000 ? -1 : ans);
        }

    }
}
