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.*;

public class Es4bis
{
    static IO io = new IO();
    public static void main(String[] args)
    {
		int n = io.getInt();
		long[] a = new long[n];
		for(int i=0; i<n; i++)
			a[i] = io.getLong();
		
		ArrayList<Integer>[] numPerBit = new ArrayList[64];
		TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
		int count =0;
		for(int i=0; i<64; i++)
			numPerBit[i] = new ArrayList<Integer>();
		boolean done = false;
		for(int i=0; !done && i<n; i++){
			for(long j=0;!done && j<64; j++){
				if((a[i]&(1L<<j)) != 0){
					numPerBit[(int)j].add(i);
					map.put(i, count);
					count++;
					if(numPerBit[(int)j].size() == 3)
						done = true;
				}
				
			}
		}
		
		
		if(done)
			io.println(3);
		else{
		adjMatrix = new int[128][128];
		for(int i=0; i<64; i++){
			if(numPerBit[i].size() < 2)
				continue;
			adjMatrix[map.get(numPerBit[i].get(0))][map.get(numPerBit[i].get(1))] = 1;
			adjMatrix[map.get(numPerBit[i].get(1))][map.get(numPerBit[i].get(0))] = 1;
			
		
		}
		
		for(int i=0; i<128; i++){
			for(int j=0; j<128; j++){
				if(adjMatrix[i][j]==1){
					adjMatrix[i][j] = 0;
					adjMatrix[j][i] = 0;
					min = Math.min(bfs(i, j)+1, min);
					adjMatrix[i][j] = 1;
					adjMatrix[j][i] = 1;
				}
			}
		}
		
		io.println(min < 1000000? min : "-1");
		
		}
        io.close();
    }
	
	static int[][] adjMatrix;
	static int min = 1000000000;
	
	static int[] dist;
	public static int bfs(int s, int t) //no recursion here
	{
		dist = new int[128]; // distances from s
		
		for(int i=0; i<128; i++)
			dist[i] = 1000000000; //inf
		dist[s] = 0; //distance from s to s = 0
		ArrayDeque<Integer> q = new ArrayDeque<Integer>();
		q.addLast(s);
		
		while(!q.isEmpty())
		{
			int v = (int)q.poll();
			for(int i=0; i < adjMatrix[v].length; i++)
			{
				if(adjMatrix[v][i] != 1)
					continue;
				//int u = (int)adjList[v].get(i);
				if(dist[i] == 1000000000)
				{
					dist[i] = dist[v] + 1;
					q.addLast(i);
				}
			}
		}
		
		return dist[t];
	}
	
}
 
 
 
class IO extends PrintWriter {
	public IO() {
        super(new BufferedOutputStream(System.out));
        r = new BufferedReader(new InputStreamReader(System.in));
    }
 
    public IO(String fileName) {
        super(new BufferedOutputStream(System.out));
        try{
            r = new BufferedReader(new FileReader(fileName));
        } catch (FileNotFoundException e) {
            this.println("File Not Found");
        }
    }
 
    public boolean hasMoreTokens() {
        return peekToken() != null;
    }
 
    public int getInt() {
        return Integer.parseInt(nextToken());
    }
 
    public double getDouble() {
        return Double.parseDouble(nextToken());
    }
 
    public long getLong() {
        return Long.parseLong(nextToken());
    }
 
    public String getWord() {
        return nextToken();
    }
 
	public String getLine(){
        try{
            st = null;
            return r.readLine();
        }
        catch(IOException ex){}
        return null;
    }
	
 
    private BufferedReader r;
    private String line;
    private StringTokenizer st;
    private String token;
 
    private String peekToken() {
        if (token == null)
            try {
                while (st == null || !st.hasMoreTokens()) {
                    line = r.readLine();
                    if (line == null) return null;
                    st = new StringTokenizer(line);
                }
                token = st.nextToken();
            } catch (IOException e) { }
        return token;
    }
 
    private String nextToken() {
        String ans = peekToken();
        token = null;
        return ans;
    }
}