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.awt.Font;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class D {
	static int mod =998244353 ;
	static long[] fac;
	static final int N = 2020; 
    @SuppressWarnings("unchecked") 
    static Vector<Integer>[]gr; 
  
    // Function to add edge 
    static void Add_edge(int x, int y) 
    { 
        gr[x].add(y); 
        gr[y].add(x); 
    } 
  
    // Function to find the length of 
    // the shortest cycle in the graph 
    static int shortest_cycle(int n) 
    { 
  
        // To store length of the shortest cycle 
        int ans = Integer.MAX_VALUE; 
  
        // For all vertices 
        for (int i = 0; i < n; i++) 
        { 
  
            // Make distance maximum 
            int[] dist = new int[n]; 
            Arrays.fill(dist, (int) 1e9); 
  
            // Take a imaginary parent 
            int[] par = new int[n]; 
            Arrays.fill(par, -1); 
  
            // Distance of source to source is 0 
            dist[i] = 0; 
            Queue<Integer> q = new LinkedList<>(); 
  
            // Push the source element 
            q.add(i); 
  
            // Continue until queue is not empty 
            while (!q.isEmpty()) 
            { 
  
                // Take the first element 
                int x = q.poll(); 
  
                // Traverse for all it's childs 
                for (int child : gr[x]) 
                { 
                    // If it is not visited yet 
                    if (dist[child] == (int) (1e9)) 
                    { 
  
                        // Increase distance by 1 
                        dist[child] = 1 + dist[x]; 
  
                        // Change parent 
                        par[child] = x; 
  
                        // Push into the queue 
                        q.add(child); 
                    } else if (par[x] != child && par[child] != x) 
                        ans = Math.min(ans, dist[x] + dist[child] + 1); 
                } 
            }
        } 
  
        // If graph contains no cycle 
        if (ans == Integer.MAX_VALUE) 
            return -1; 
  
        // If graph contains cycle 
        else
            return ans; 
    } 
  
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		int n = sc.nextInt();
		int[] bits = new int[65];
		long[] arr = new long[n];
		long[] arr2 = new long[n];
		int k=0;
		for(int i=0;i<arr.length;i++) {
			arr[i] = sc.nextLong();
			for(int j=0;j<60;j++) {
				bits[j]+=((1l<<j & arr[i])!=0)?1:0;
			}if(arr[i]!=0)
				arr2[k++]=arr[i];
		}
		n=k;
		boolean f = false;
		for(int i=0;i<bits.length;i++) {
			if(bits[i]>=3) {
				f = true;
			}
		}
		if(f) {
			pw.println(3);
		}else {
			gr = new Vector[n+5];
		       for (int i = 0; i < n+5; i++) 
		            gr[i] = new Vector<>(); 
			for(int i=0;i<n;i++) {
				for(int j=i+1;j<n;j++) {
					if((arr2[i]&arr2[j])!=0)
						Add_edge(i, j);
				}
			}
			pw.println(shortest_cycle(n));
		}
		pw.flush();
		pw.close();
	}
	
	public static long ncr(int n , int r ) {
		if(n<r) return 0;
		long ans=fac[n];
		ans=(ans*powmod(fac[n-r], mod-2, mod))%mod;
		ans=(ans*powmod(fac[r], mod-2, mod))%mod;
		return ans;
	}
	static int log(long n, long r) 
	{ 
	    return (n > r - 1) ? 1 + log(n / r, r) : 0; 
	} 
	 
	 
	public static long powmod(long x ,int p,int mod) {// loop O(log p )
		long ans=1;
		x%=mod;
		while(p>0) {
			
			if((p&1)==1) 
				ans= (ans*x)%mod;
		x=(x*x)%mod;
		p>>=1;
		}
		return ans;
	}
}
class Scanner {
    StringTokenizer st;
    BufferedReader br;
 
    public Scanner(FileReader r) {
        br = new BufferedReader(r);
    }
 
    public Scanner(InputStream s) {
        br = new BufferedReader(new InputStreamReader(s));
    }
 
    public String next() throws IOException {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }
 
    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
 
    public long nextLong() throws IOException {
        return Long.parseLong(next());
    }
 
    public String nextLine() throws IOException {
        return br.readLine();
    }
 
    public double nextDouble() throws IOException {
        String x = next();
        StringBuilder sb = new StringBuilder("0");
double res = 0, f = 1;
boolean dec = false, neg = false;
int start = 0;
if (x.charAt(0) == '-') {
    neg = true;
    start++;
}
for (int i = start; i < x.length(); i++)
    if (x.charAt(i) == '.') {
        res = Long.parseLong(sb.toString());
        sb = new StringBuilder("0");
            dec = true;
        } else {
            sb.append(x.charAt(i));
            if (dec)
                f *= 10;
        }
    res += Long.parseLong(sb.toString()) / f;
    return res * (neg ? -1 : 1);
}

public boolean ready() throws IOException {
    return br.ready();
    
}
}