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.
/**
 * @author derrick20
 */
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class ShortestCycle {
    public static void main(String args[]) throws Exception {
        FastScanner sc = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int N = sc.nextInt();
        adjList = new ArrayList[N];
        buckets = new HashMap<>();
        for (int i = 0; i <= 60; i++) {
            buckets.put(i, new ArrayList<>());
        }
        HashSet<Long> values = new HashSet<>();
        for (int i = 0; i < N; i++) {
            long v = sc.nextLong();
            long temp = v;
            int bucket = 0;
            while (temp > 0) {
                if ((temp & 1) > 0) {
                    buckets.get(bucket).add(v);
                    values.add(v);
                }
                temp >>= 1;
                bucket++;
            }
        }
        boolean found3 = false;
        for (Integer bucket : buckets.keySet()) {
            if (buckets.get(bucket).size() >= 3) {
                found3 = true;
                break;
            }
        }
        if (found3) {
            out.println(3);
        }
        else {
            int shortestCycle = oo;
            // This ensures that there are only 120 nodes at most. We can literally just bfs from each one now
            for (Long source : values) {
                HashMap<Long, Integer> visited = new HashMap<>();
                for (Long val : values) {
                    visited.put(val, 0);
                }
                ArrayDeque<Long> queue = new ArrayDeque<>();
                HashMap<Long, Integer> dist = new HashMap<>();
                HashMap<Long, Long> parent = new HashMap<>();

                parent.put(source, source);
                queue.add(source);
                dist.put(source, 0);
                bfs : while (queue.size() > 0) {
                    Long top = queue.removeFirst();
                    visited.put(top, 2);
                    long temp = top;
                    int bucket = 0;
                    while (temp > 0) {
                        if ((temp & 1) > 0) {
                            for (Long adj : buckets.get(bucket)) {
                                if (adj.equals(top)) continue;
                                if (visited.get(adj).equals(0)) {
                                    visited.put(adj, 1);
                                    queue.add(adj);
                                    dist.put(adj, dist.get(top) + 1);
                                    parent.put(adj, top);
                                }
                                else {
                                    // Ahah! found the cycle
                                    // Key issue: with something that branches to many repeated edges (parallel edges),
                                    // we may see an edge that we just visited,
                                    if (!parent.get(top).equals(adj) && visited.get(adj).equals(2)) {
                                        shortestCycle = Math.min(shortestCycle, dist.get(top) + dist.get(adj) + 1);
//                                        System.out.println("Top : " + top + " " + " Adj : " + adj + " " + shortestCycle);
                                        break bfs;
                                    }
                                }
                            }
                        }
                        temp >>= 1;
                        bucket++;
                    }
                }
//                System.out.println("Source: " + source + "\t Distances: " + dist);
            }
            out.println(shortestCycle == oo ? -1 : shortestCycle);
        }
        out.close();
    }

    static ArrayList<Long>[] adjList;
    static HashMap<Integer, ArrayList<Long>> buckets;
    static int oo = (int) 1e9;

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        FastScanner(FileReader s) {
            br = new BufferedReader(s);
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        String nextLine() throws IOException { return br.readLine(); }

        double nextDouble() throws IOException { return Double.parseDouble(next()); }

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

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