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.
import java.io.*;
import java.util.*;

public class Main {

    public Map <Long, Set <Long>> ver = new HashMap<>();
    public Vector <Integer> bitsArray = new Vector<>();
    public Vector <Long>[] bit = new Vector[65];

    public class Pair<X, Y>{
        public X x;
        public Y y;
        Pair(X x, Y y){
            this.x = x;
            this.y = y;
        }
    }

    public int cycle(Map <Long, Set <Long>> ver, long v, Map <Long, Boolean> used, long u){
        int res = Integer.MAX_VALUE;
        Queue <Pair <Long, Integer>> q = new ArrayDeque<>();
        q.add(new Pair<Long, Integer>(v, 1));
        while(!q.isEmpty() == true){
            Pair<Long, Integer> p = q.poll();
            Long vertix = p.x;
            Integer d = p.y;
            boolean ok = false;
            for (Long g : ver.get(vertix)){
                if (vertix == v && g == u)continue;
                if (!used.containsKey(g) || used.get(g) != true){
                    if (g == u){
                        ok = true;
                        res = d + 1;
                        break;
                    }
                    q.add(new Pair<Long, Integer>(g, d + 1));
                    used.put(g, true);
                }
            }
            if (ok == true){
                break;
            }
        }
        return res;
    }

    public void solve(InputReader in, PrintWriter out){
        int n = in.nextInt();
        for (int i = 0; i < 65; i++)
            bit[i] = new Vector<>();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextLong();
            for (long j = 0; j < 65L; j++){
                if (((1L << j) & arr[i]) != 0L){
                    int idx = (int)j;
                    bit[idx].add(arr[i]);
                    if (bit[idx].size() == 3){
                        out.print("3\n");
                        return;
                    }
                }
            }
        }
        int answ = Integer.MAX_VALUE;

        for (int i = 0; i < 65; i++){
            if (bit[i].size() == 2){
                if (ver.get(bit[i].get(0)) == null) {
                    ver.put(bit[i].get(0), new HashSet<>());
                }
                if (ver.get(bit[i].get(1)) == null) {
                    ver.put(bit[i].get(1), new HashSet<>());
                }
                ver.get(bit[i].get(0)).add(bit[i].get(1));
                ver.get(bit[i].get(1)).add(bit[i].get(0));
            }
        }
        for (int i = 0; i < 65; i++){
            if (bit[i].size() == 2){
                Map <Long, Boolean> used = new HashMap<>();
                int answ0 = cycle(ver, bit[i].get(0), used, bit[i].get(1));
                answ = Math.min(answ, answ0);
            }
        }
        if (answ == Integer.MAX_VALUE){
            out.print("-1\n");
        }else{
            out.println(answ);
        }
    }

    public static void main( String[] args ) {

        BufferedReader bis = new BufferedReader(new InputStreamReader(System.in));
        // BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);

        Main solution = new Main();
        solution.solve(in, out);
        out.flush();
    }


    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}