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.
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
*/
import java.util.*;
import java.io.*;

   public class x1206D
   {
      public static void main(String args[]) throws Exception
      {
         //BufferedReader infile = new BufferedReader(new FileReader("cowdate.in"));
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         long[] arr = readArr2(N, infile, st);
         //solve
         for(int bit=0; bit < 70; bit++)
         {
            int cnt = 0;
            for(long x: arr)
               if((x & (1L << bit)) > 0)
                  cnt++;
            if(cnt >= 3)
            {
               System.out.println(3);
               return;
            }
         }
         LinkedList<Integer>[] edges = new LinkedList[N+1];
         for(int i=1; i <= N; i++)
            edges[i] = new LinkedList<Integer>();
         for(int bit=0; bit < 70; bit++)
         {
            ArrayList<Integer> ls = new ArrayList<Integer>();
            for(int i=0; i < N; i++)
            {
               long x = arr[i];
               if((x & (1L << bit)) > 0)
                  ls.add(i);
            }
            if(ls.size() > 1)
            {
               int a = (int)ls.get(0)+1;
               int b = (int)ls.get(1)+1;
               edges[a].add(b);
               edges[b].add(a);
            }
         }
         //dfs
         //this isn't hard
         //O(N*M)
         int res = Integer.MAX_VALUE;
         for(int i=1; i < N; i++)
            for(int j: edges[i])
            {
               if(i > j)
                  continue;
               boolean[] seen = new boolean[N+1];
               Queue<State> q = new LinkedList<State>();
               q.add(new State(i, 1));
               seen[i] = true;
               outer:while(q.size() > 0)
               {
                  State curr = q.poll();
                  for(int next: edges[curr.id])
                  {
                     if(!seen[next] && !(curr.id == i && next == j))
                     {
                        State c2 = new State(next, curr.d+1);
                        seen[next] = true;
                        q.add(c2);
                     }
                     if(next == i && curr.id == j)
                     {
                        res = Math.min(res, curr.d);
                        break outer;
                     }
                  }
               }
            }
         if(res == Integer.MAX_VALUE)
            System.out.println(-1);
         else
            System.out.println(res);
      }
      public static boolean drunk(long[] arr)
      {
         HashSet<Long> set = new HashSet<Long>();
         for(long x: arr)
            set.add(x);
         return set.size() != arr.length;
      }
      //input shenanigans
      public static long[] readArr2(int N, BufferedReader infile, StringTokenizer st) throws Exception
      {
         long[] arr = new long[N];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < N; i++)
            arr[i] = Long.parseLong(st.nextToken());
         return arr;
      }
   }
   class State
   {
      public int id;
      public int d;
      
      public State(int a, int b)
      {
         id = a;
         d = b;
      }
   }