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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import javafx.util.Pair;

public class Solve5 {

    public static void main(String[] args) throws IOException {
        PrintWriter pw = new PrintWriter(System.out);
        new Solve5().solve(pw);
        pw.flush();
        pw.close();
    }

    public void solve(PrintWriter pw) throws IOException {
        FastReader sc = new FastReader();
        int n = sc.nextInt();
        int[] cnt = new int[65];
        ArrayList<Long> a = new ArrayList();
        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            if (x == 0) {
                continue;
            }
            for (int j = 0; j < 64; j++) {
                if ((x & ((long) 1 << j)) != 0) {
                    cnt[j]++;
                    if (cnt[j] == 3) {
                        pw.println(3);
                        return;
                    }
                }
            }
            a.add(x);
        }
        n = a.size();
        HashSet<Integer>[] adj = new HashSet[n + 1];
        LinkedList<Pair<Integer, Integer>> edges = new LinkedList();
        for (int i = 1; i <= n; i++) {
            adj[i] = new HashSet();
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((a.get(i) & a.get(j)) != 0) {
                    adj[i + 1].add(j + 1);
                    adj[j + 1].add(i + 1);
                    edges.add(new Pair(i + 1, j + 1));
                }
            }
        }
        long min = Integer.MAX_VALUE;
        for (Pair<Integer, Integer> edge : edges) {
            int u = edge.getKey(), v = edge.getValue();
            adj[u].remove(v);
            adj[v].remove(u);
            min = Math.min(min, dijkstra(adj, u, v) + 1);
            adj[u].add(v);
            adj[v].add(u);
        }
        pw.println(min == Integer.MAX_VALUE ? -1 : min);
    }

    public long dijkstra(HashSet<Integer>[] adj, int u, int v) {
        int n = adj.length;
        int[] dist = new int[n];
        boolean[] vis = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (i != u) {
                dist[i] = Integer.MAX_VALUE;
            }
        }
        Comparator<Integer> cmp = new Comparator<Integer>() {
            @Override
            public int compare(Integer p1, Integer p2) {
                return dist[p1] - dist[p2];
            }
        };
        PriorityQueue<Integer> p = new PriorityQueue(cmp);
        p.add(u);
        while (!p.isEmpty()) {
            int node = p.poll();
            vis[node] = true;
            for (Integer next : adj[node]) {
                if (!vis[next] && dist[node] + 1 < dist[next]) {
                    dist[next] = dist[node] + 1;
                    p.add(next);
                }
            }
        }
        return dist[v];
    }

    static class FastReader {

        StringTokenizer st;
        BufferedReader br;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

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

        public boolean hasNext() throws IOException {
            if (st != null && st.hasMoreTokens()) {
                return true;
            }
            String s = br.readLine();
            if (s == null || s.isEmpty()) {
                return false;
            }
            st = new StringTokenizer(s);
            return true;
        }

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

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

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

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