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.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Solution{
	
	
	static ArrayList<Integer>[] adjlist;
	static int n;
	static final int inf = (int)1e9;
	static int ans = inf;
	static int[] q;
	
	
	
    public static void main(String[] args) throws IOException {
     
    	FastScanner fs = new FastScanner();
    	PrintWriter out = new PrintWriter(System.out);
    	
    		
    		
    	int tt = 1;
    	while(tt-->0) {
    		
    		n = fs.nextInt();
    		long[] a = new long[n];
    		for(int i=0;i<n;i++) {
    			a[i] = fs.nextLong();
    			//remove zeros because there can be any number of zeroes  which will give TLE
    			if(a[i]==0) {
    				i--;
    				n--;
    			}
    		}
    		
    		
    		int[] cnt = new int[61];
    		
    		for(int i=0;i<n;i++) {
    			for(int j=0;j<=60;j++) {
    				if(((1L<<j)&a[i])!=0) {
    					cnt[j]++;
    					int x = 1;
    					if(cnt[j]>=3) {
    						out.println(3);
    						out.flush();
    						return;
    					}
    				}
    			}
    		}
    		
    		//now n <= 120 because each bit is contained in atmost two numbers 
    		adjlist = new ArrayList[n];
    		for(int i=0;i<n;i++) adjlist[i] = new ArrayList<Integer>();
    		
    		for(int i=0;i<n;i++) {
    			for(int j=i+1;j<n;j++) {
    				if((a[i]&a[j])!=0) {
    					adjlist[i].add(j);
    					adjlist[j].add(i);
    				}
    			}
    		}
    		
    		//queue
    		q = new int[n];
    		
    		for(int i=0;i<n;i++) {
    			bfs(i);
    		}
    		
    		if(ans==inf) 
    			out.println(-1);
    		else
    			out.println(ans);
    		
    	}
    	
    		
    		
    		
    	out.close();
    		
    }
    
    
    //finds shortest cycle passing through the source vertex.
    static void bfs(int src) {
    	
    	int[] dis = new int[n];
    	Arrays.fill(dis, inf);
    	
    	//queue implementation with array
    	int topq = 0;
    	q[topq++] = src;
    	dis[src] = 0;
    	
    	
    	for(int i=0;i<topq;i++) {
    		int cur = q[i];
    		
    		for(int v: adjlist[cur]) {
    			if(dis[v]==inf) {
    				dis[v] = 1 + dis[cur];
    				q[topq++] = v;
    			}
    			else if(dis[v]>=dis[cur]) {
    				ans = Math.min(ans, dis[v] + dis[cur] + 1);
    			}
    				
    		}
    	}
    	
    	
    }
    
  
    
    
    
    
    static final Random random=new Random();
    	
    static void ruffleSort(int[] a) {
    	int n=a.length;//shuffle, then sort 
    	for (int i=0; i<n; i++) {
    		int oi=random.nextInt(n); int temp=a[oi];
    		a[oi]=a[i]; a[i]=temp;
    	}
    	Arrays.sort(a);
    }
   
  
    
    	
    	
    static class FastScanner{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer("");
     
    	public String next(){
    		while(!st.hasMoreElements()){
    			try{
    				st = new StringTokenizer(br.readLine());
    			} catch(IOException e){
    				e.printStackTrace();
    			}
    		}
    		return st.nextToken();
    	}
    		
    	public String nextLine() throws IOException {
    		return br.readLine();
    	}
    		
    	public int nextInt(){
    		return Integer.parseInt(next());
    	}
     
    	public int[] readArray(int n){
    		int[] a = new int[n];
    		for(int i=0;i<n;i++)
    			a[i] = nextInt();
    		return a;
    	}
    		
    	public long nextLong() {
    		return Long.parseLong(next());
    	}
    		
    	public char nextChar() {
    		return next().toCharArray()[0];
    	}
    }
   	
}
