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.
#include <bits/stdc++.h>
using namespace std;
struct lyrics {
  string line1;
  string line2;
};
struct myp {
  int f;
  int s;
};
struct edges {
  int v;
  bool check1;
};
struct mypair {
  string f;
  string s;
};
int dx[5] = {-1, 0, 0, 1, 0};
int dy[5] = {0, 1, -1, 0, 0};
bool go[100008];
int dis[100009];
string process(long long num) {
  string ans = "";
  if (num == 0)
    ans += '0';
  else {
    while (num != 0) {
      if (num % 2 == 0)
        ans += '0';
      else
        ans += '1';
      num = num / 2;
    }
  }
  while (ans.size() < 62) ans += '0';
  reverse(ans.begin(), ans.end());
  return ans;
}
long long calculatingpowWithRemain(long long pow, long long base,
                                   long long remain) {
  long long ans = 1;
  for (int i = 0; i < pow; i++) ans = (ans * base) % remain;
  return ans;
}
int convert(int x) {
  if (x == 4) return 0;
  if (x == 8) return 1;
  if (x == 15) return 2;
  if (x == 16) return 3;
  if (x == 23) return 4;
  if (x == 42) return 5;
}
long long gcd(long long a, long long b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
long long mypow2(long long n) {
  long long ans = 1;
  for (int i = 0; i < n; i++) ans *= 2;
  return ans;
}
bool isok(int n, int m, int x, int y, char** a) {
  if (x >= 0 && x < n && y >= 0 && y < m) {
    return true;
    return false;
  }
  return false;
}
int logbase2(int n) {
  int ans = n;
  int count = 0;
  while (ans != 1) {
    ans /= 2;
    count += 1;
  }
  return count;
}
int gcd(int num, int denum) {
  if (num == 0)
    return denum;
  else
    return gcd(denum % num, num);
}
int myabs(int a) {
  if (a >= 0)
    return a;
  else
    return -a;
}
bool checkpls(string a, string b) {
  if (a == b) return true;
  if (a[1] == b[1] && abs(a[0] - b[0]) <= 2) return true;
  return false;
}
void resetdis() {
  for (int i = 0; i < 100009; i++) dis[i] = 0;
}
int goBFS(int source, int end, vector<int>* edges) {
  queue<int> tui;
  tui.push(source);
  while (!(tui.empty())) {
    int get = tui.front();
    tui.pop();
    for (int ver : edges[get]) {
      if (!(get == source && ver == end)) {
        if (dis[ver] == 0 && ver != source) {
          dis[ver] = dis[get] + 1;
          tui.push(ver);
        }
        if (ver == end) return dis[ver];
      }
    }
  }
  return -1;
}
int main() {
  int n;
  cin >> n;
  vector<int> savepos[62];
  long long* a;
  a = new long long[n];
  bool existthreee = false;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    string tmp = process(a[i]);
    for (int j = 0; j < 62; j++) {
      if (tmp[j] == '1') {
        savepos[j].push_back(i);
        if (savepos[j].size() == 3) existthreee = true;
      }
    }
  }
  if (existthreee == true)
    cout << "3";
  else {
    vector<int>* edges;
    vector<myp> edges1;
    edges = new vector<int>[n];
    for (int i = 0; i < 62; i++) {
      if (savepos[i].size() == 2) {
        edges[savepos[i][0]].push_back(savepos[i][1]);
        edges[savepos[i][1]].push_back(savepos[i][0]);
        edges1.push_back(myp{savepos[i][0], savepos[i][1]});
      }
    }
    int mymin = INT_MAX;
    for (int i = 0; i < edges1.size(); i++) {
      int ans = goBFS(edges1[i].f, edges1[i].s, edges);
      if (ans != -1) mymin = min(mymin, ans);
      resetdis();
    }
    if (mymin == INT_MAX)
      cout << "-1";
    else
      cout << mymin + 1;
  }
}
