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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Round560D {

	
	public static class Pair implements Comparable<Pair>{
		int id;
		int distance;
		
		public Pair(int id,int distance) {
			this.id=id;
			this.distance=distance;
		}
		
		public int compareTo(Pair x) {
			return this.distance-x.distance;
		}
	}
	
	public static HashSet<Integer>[] adj;
	public static LinkedList<Integer>[] adj2;
	
	public static int Dijkstra(int u,int v) {
		int n=adj.length;
		int[] ans=new int[n];
		Arrays.fill(ans, Integer.MAX_VALUE);
		ans[u]=0;
		boolean[] spset=new boolean[n];
		PriorityQueue<Pair> min=new PriorityQueue<>();
		min.add(new Pair(u,0));
		while(!min.isEmpty()) {
			while(!min.isEmpty()) {
				Pair top = min.peek();
				if(spset[top.id]) {
					min.poll();
				}else {
					break;
				}
			}
			if(min.isEmpty())break;
			Pair top =min.poll();
			for(Integer x:adj[top.id]) {
				if(top.distance+1<ans[x]) {
					ans[x]=top.distance+1;
				}
				min.add(new Pair(x,ans[x]));
			}
			spset[top.id]=true;
		}
		return ans[v];
	}

	public static int Dijkstra_Util() {
		int n=adj.length;
		int min =Integer.MAX_VALUE;
		for(int i=0;i<n;i++) {
			for(Integer x:adj2[i]) {
				adj[x].remove(i);
				adj[i].remove(x);
				int value = Dijkstra(i, x);
				if(value == Integer.MAX_VALUE) { 
				}else {
					min = Integer.min(min, value+1);
				}
				adj[x].add(i);
				adj[i].add(x);
			}
		}
		return min;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		out=new PrintWriter(new BufferedOutputStream(System.out));
		FastReader s=new FastReader();
		int n=s.nextInt();
		int[][] helper=new int[n][65];
		adj=new HashSet[n];
		adj2=new LinkedList[n];
		for(int i=0;i<n;i++)adj[i]=new HashSet<>();
		for(int i=0;i<n;i++)adj2[i]=new LinkedList<>();
		for(int i=0;i<n;i++) {
			long x=s.nextLong();
			String bs=Long.toBinaryString(x);
			for(int j=0,k=bs.length()-1;j<65 && k>=0 ;j++,k-- ) {
				helper[i][j]=bs.charAt(k)-'0';
			}
		}
		for(int i=0;i<65;i++) {
			int count=0;
			for(int j=0;j<n;j++) {
				count+=helper[j][i];
			}
			if(count>=3) {
				out.print(3);
				out.close();
				return;
			}
		}
		for(int i=0;i<65;i++) {
			int first=-1;
			int second =-1;
			for(int j=0;j<n;j++) {
				if(helper[j][i]==1) {
					if(first == -1) {
						first = j;
					}else {
						second = j;
					}
				}
			}
			if(first !=-1 && second !=-1) {
				adj[first].add(second);
				adj[second].add(first);
				adj2[first].add(second);
				adj2[second].add(first);
			}
		}
		int ans = Dijkstra_Util();
		if(ans == Integer.MAX_VALUE) {
			out.print(-1);
		}else {
			out.print(ans);
		}
		out.close();
	}

	public static PrintWriter out;
	
	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;
		//it reads the data about the specified point and divide the data about it ,it is quite fast
		//than using direct 

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
			//InputStream reads the data and decodes in character stream
			//It acts as bridge between byte stream and character stream
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());//converts string to integer
		}

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

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

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception e) {
				e.printStackTrace();
			}
			return str;
		}
	}
	
}
