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.*;
import java.math.BigInteger;
import java.util.Map.Entry;

import static java.lang.Math.*;

public class B extends PrintWriter {

    void run() {

        int n = nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextLong();

            int j = rnd.nextInt(i + 1);

            long tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }

        int m = 63;
        int[] cnt = new int[m];
        for (int i = 0; i < n; i++) {
            long val = a[i];
            for (int b = 0; b < m; b++) {
                if ((val & 1) != 0) {
                    ++cnt[b];
                }
                val >>>= 1;
            }
        }

        for (int v : cnt) {
            if (v >= 3) {
                println(3);
                return;
            }
        }

        Arrays.sort(a);

        int nz = 0;
        while (nz < n && a[nz] == 0) {
            ++nz;
        }

        a = Arrays.copyOfRange(a, nz, n);
        n = a.length;

        List<Integer>[] g = new List[n];

        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<Integer>(n);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if ((a[i] & a[j]) != 0) {
                    g[i].add(j);
                    g[j].add(i);
                }
            }
        }

        int inf = n + 1;

        int min = inf;

        int[] d = new int[n];
        int[] q = new int[n];
        int[] p = new int[n];

        for (int s = 0; s < n; s++) {
            Arrays.fill(d, inf);
            int h = 0, t = 0;

            q[t++] = s;

            p[s] = -1;
            d[s] = 0;

            while (h != t) {
                int u = q[h++];

                for (int v : g[u]) {
                    if (v == p[u]) {
                        continue;
                    }

                    min = min(min, d[u] + d[v] + 1);

                    if (d[v] == inf) {
                        d[v] = d[u] + 1;
                        p[v] = u;
                        q[t++] = v;

                    }

                }

            }

        }

        if (min < inf) {
            println(min);
        } else {
            println(-1);
        }

    }

    void skip() {
        while (hasNext()) {
            next();
        }
    }

    int[][] nextMatrix(int n, int m) {
        int[][] matrix = new int[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                matrix[i][j] = nextInt();
        return matrix;
    }

    String next() {
        while (!tokenizer.hasMoreTokens())
            tokenizer = new StringTokenizer(nextLine());
        return tokenizer.nextToken();
    }

    boolean hasNext() {
        while (!tokenizer.hasMoreTokens()) {
            String line = nextLine();
            if (line == null) {
                return false;
            }
            tokenizer = new StringTokenizer(line);
        }
        return true;
    }

    int[] nextArray(int n) {
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = nextInt();
        }
        return array;
    }

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

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

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

    String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException err) {
            return null;
        }
    }

    public B(OutputStream outputStream) {
        super(outputStream);
    }

    static BufferedReader reader;
    static StringTokenizer tokenizer = new StringTokenizer("");
    static Random rnd = new Random();
    static boolean OJ;

    public static void main(String[] args) throws IOException {
        OJ = System.getProperty("ONLINE_JUDGE") != null;
        B solution = new B(System.out);
        if (OJ) {
            reader = new BufferedReader(new InputStreamReader(System.in));
            solution.run();
        } else {
            reader = new BufferedReader(new FileReader(new File(B.class.getName() + ".txt")));
            long timeout = System.currentTimeMillis();
            while (solution.hasNext()) {
                solution.run();
                solution.println();
                solution.println("----------------------------------");
            }
            solution.println("time: " + (System.currentTimeMillis() - timeout));
        }
        solution.close();
        reader.close();
    }
}