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.FileNotFoundException;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;


public class B1205 {
	
	private static class Edge {
		long w;
		int n1;
		int n2;
		
		Edge(long w,int n1,int n2) {
			this.w = w;
			this.n1 = n1;
			this.n2 = n2;
		}
	}
	
	private static class Node {
		long h;
		ArrayList<Edge> edges = new ArrayList<Edge>();
		
		Node(long h) {
			this.h = h;
		}
	}
	
	private static Node[] G = new Node[1000];
	
	private static int cnt = 0;
	
	public static void main(String[] args) throws Exception {
//		BufferedReader br = new BufferedReader(new FileReader("F:/books/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Integer n = Integer.parseInt(br.readLine());
		ArrayList<ArrayList<Node>> ll = new ArrayList<ArrayList<Node>>();
		for(int i=0;i<64;i++) ll.add(new ArrayList<Node>());
		String[] s1 = br.readLine().split(" ");
		Long[] a = new Long[s1.length];
		for (int i = 0; i < s1.length; i++) {
			a[i] = Long.parseLong(s1[i]);
		}
		for(int i=0;i<s1.length;i++) {
			process(a[i],ll);
		}
		long min = Long.MAX_VALUE;
		for(int i=1;i<1000;i++) {
			if(G[i]==null) break;
			ArrayList<Edge> edges = (ArrayList<Edge>) G[i].edges.clone();
			for(Edge e : edges) {
				G[i].edges.remove(e);
				long[] d = Djikstra(G,i);
				if(d[e.n2]!=Long.MAX_VALUE) d[e.n2]++;
				min = Math.min(min, d[e.n2]);
				G[i].edges.add(e);
			}
		}
		if(min==Long.MAX_VALUE) min = -1;
		System.out.println(min);
	}

	private static void process(Long n, ArrayList<ArrayList<Node>> ll) {
		if(n==0) return;
		long b = 0x1;
		++cnt;
		G[cnt] = new Node(cnt);
		for(int i=0;i<64;i++) {
			if((n&b)!=0) {
				ArrayList<Node> list = ll.get(i);
				if(list.size()==2) {
					System.out.println("3");
					System.exit(0);
				}
				if(list.size()==1) {
					Node id = list.get(0);
					boolean fl = false;
					for(Edge e : G[cnt].edges) if(e.n2==id.h) {
						fl = true;
						break;
					}
					if(!fl) {
						id.edges.add(new Edge(1,(int) id.h,cnt));
						G[cnt].edges.add(new Edge(1,cnt,(int) id.h));
					}
				}
				list.add(G[cnt]);
			}
			b = b<<1;
		}
	}
	
	private static long[] Djikstra(Node[] G,int s) {
		int l = G.length;
		long[] dist = new long[l];
		boolean[] visited = new boolean[l];
		for(int i=0;i<l;i++) dist[i]=Long.MAX_VALUE;
		PriorityQueue<Pair> Q = new PriorityQueue<Pair>();
		Q.add(new Pair(0,s));
		while(!Q.isEmpty()) {
			Pair p = Q.poll();
			int n = (int) p.second;
			if(visited[n]) continue;
			dist[n] = p.first;
			for(Edge e : G[n].edges) {
				int n2 = (e.n1==n)?e.n2:e.n1;
				if(!visited[n2]) Q.add(new Pair(p.first+e.w,n2));
			}
			visited[n]=true;
		}
		return dist;
	}

	private static class Pair implements Comparable<Pair>{
		long first;
		long second;

		Pair(long first, long second) {
			this.first = first;
			this.second = second;
		}

		@Override
		public int compareTo(Pair p) {
			if(first>p.first) return 1;
			else if(first<p.first)return -1;
			else if(second>p.second) return 1;
			else if(second<p.second) return -1;
			return 0;
		}
	}

}
