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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.AbstractQueue;
import java.util.Random;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.Comparator;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            long[] a = new long[n];
            int cntZeros = 0;
            for (int i = 0; i < n; i++) {
                a[i] = in.nextLong();
                if (a[i] == 0)
                    cntZeros++;
            }
            int[] cnts = new int[64];
            long k = 1;
            for (int i = 0; i <= 63; i++, k <<= 1) {
                for (int j = 0; j < n; j++) {
                    if ((a[j] & k) == k) {
                        cnts[i]++;
                    }
                }
            }
            for (int i = 0; i < cnts.length; i++) {
                if (cnts[i] > 2) {
                    out.println(3);
                    return;
                }
            }

            ArrayUtils.shuffle(a);
            Arrays.sort(a);

            int[][] g = new int[n - cntZeros][n - cntZeros];
            ArrayList<PairIntInt> edges = new ArrayList<>();
            for (int i = cntZeros; i < n - 1; i++) {
                for (int j = i + 1; j < n; j++)
                    if ((a[i] & a[j]) != 0) {
                        g[i - cntZeros][j - cntZeros] = 1;
                        g[j - cntZeros][i - cntZeros] = 1;
                        edges.add(new PairIntInt(i - cntZeros, j - cntZeros));
                    }
            }

            long minCycle = Integer.MAX_VALUE;
            long[] dist = new long[n];
            for (PairIntInt edge : edges) {
                g[edge.first][edge.second] = g[edge.second][edge.first] = 0;
                UndirectGraphUtils.dijkstra(g, edge.first, dist);
                minCycle = Math.min(dist[edge.second], minCycle);
                g[edge.first][edge.second] = g[edge.second][edge.first] = 1;
            }

            if (minCycle != Integer.MAX_VALUE) {
                out.println(minCycle + 1);
                return;
            }

            out.println(-1);
        }

    }

    static class PairIntInt {
        public int first;
        public int second;

        public PairIntInt(int first, int second) {
            this.first = first;
            this.second = second;
        }

        public boolean equals(Object obj) {
            if (obj == null)
                return false;
            if (!(obj instanceof PairIntInt))
                return false;
            PairIntInt pii = (PairIntInt) obj;
            return pii.first == first && pii.second == first;
        }

        public int hashCode() {
            return 31 * first + second;
        }

        public String toString() {
            return first + " " + second;
        }

    }

    static class UndirectGraphUtils {
        private final static PriorityQueue<PairIntLong> pq = new PriorityQueue<>(Comparator.comparingLong(o -> o.second));
        private final static HashSet<Integer> set = new HashSet<>();

        public static void dijkstra(int[][] g, int src, long[] dist) {
            assert g.length == dist.length;
            Arrays.fill(dist, Long.MAX_VALUE);
            pq.clear();
            set.clear();
            pq.add(new PairIntLong(src, 0));
            dist[src] = 0;
            while (pq.size() > 0) {
                int u = pq.remove().first;
                set.add(u);
                for (int to = 0; to < g.length; to++)
                    if (g[to][u] != 0) {
                        if (!set.contains(to)) {
                            if (dist[u] + 1 < dist[to])
                                dist[to] = dist[u] + 1;
                            pq.add(new PairIntLong(to, dist[to]));
                        }
                    }
            }
        }

    }

    static class PairIntLong {
        public int first;
        public long second;

        public PairIntLong(int first, long second) {
            this.first = first;
            this.second = second;
        }

        public boolean equals(Object obj) {
            if (obj == null)
                return false;
            if (!(obj instanceof PairIntInt))
                return false;
            PairIntInt pii = (PairIntInt) obj;
            return pii.first == first && pii.second == first;
        }

        public int hashCode() {
            int result = 31 * first + (int) (second ^ (second >>> 32));
            return result;
        }

        public String toString() {
            return first + " " + second;
        }

    }

    static final class ArrayUtils {
        static Random rnd = new Random();

        public static void shuffle(long[] ar) {
            for (int i = ar.length - 1; i > 0; i--) {
                int index = rnd.nextInt(i + 1);
                long a = ar[index];
                ar[index] = ar[i];
                ar[i] = a;
            }
        }

    }

    static class InputReader {
        StringTokenizer st;
        BufferedReader br;

        public InputReader(InputStream is) {
            BufferedReader br = new BufferedReader(new InputStreamReader(is));
            this.br = br;
        }

        public String next() {
            if (st == null || !st.hasMoreTokens()) {
                String nextLine = null;
                try {
                    nextLine = br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (nextLine == null)
                    return null;
                st = new StringTokenizer(nextLine);
            }
            return st.nextToken();
        }

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

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

    }
}

