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;
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable : 4996)
long long lgput(long long a, long long b, long long MOD) {
  long long ret = 1LL;
  while (b) {
    if (b & 1LL) ret = (ret * a) % MOD;
    a = (a * a) % MOD;
    b >>= 1LL;
  }
  return (ret % MOD);
}
long long inv_mod(long long x, long long MOD) { return lgput(x, MOD - 2, MOD); }
long long GCD(long long a, long long b) {
  long long c;
  while (b) {
    c = a % b;
    a = b;
    b = c;
  }
  return a;
}
long long LCM(long long a, long long b) { return (a * b) / GCD(a, b); }
long long big_rand() { return 1LL * rand() * RAND_MAX + rand(); }
long long xtime() { return clock() * 1000LL / CLOCKS_PER_SEC; }
bool exist(double nr, double eps) { return (nr < -eps) || (nr > eps); }
long long modd(long long nr, long long MOD) { return ((nr % MOD) + MOD) % MOD; }
void start() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cout << setprecision(10) << fixed;
  srand(time(nullptr));
}
const mt19937 rng(time(nullptr));
const double PI = acos(-1);
const double eps = 1e-6;
const long long inf = 1e9;
const long long MOD = 1e9 + 7;
const long long MAXN = 1e5 + 10;
const long long LOG = 64;
struct nod {
  int x, y;
};
int n;
long long v[MAXN];
vector<int> ans[LOG];
vector<int> gr[MAXN];
int used[MAXN];
int dp[MAXN];
queue<pair<int, int> > q;
void read() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> v[i];
    if (v[i] == 0) {
      i--;
      n--;
    }
  }
}
int bfs(int start) {
  for (int i = 1; i <= n; i++) {
    used[i] = 0;
  }
  int ret = inf;
  q.push({start, 0});
  used[start] = 1;
  dp[start] = 0;
  while (!q.empty()) {
    pair<int, int> now = q.front();
    q.pop();
    for (auto& x : gr[now.first]) {
      if (x == now.second) {
        continue;
      }
      if (!used[x]) {
        used[x] = 1;
        dp[x] = dp[now.first] + 1;
        q.push({x, now.first});
      } else if (dp[x] + dp[now.first] + 1 > 2) {
        ret = min(ret, dp[x] + dp[now.first] + 1);
      }
    }
  }
  return ret;
}
void solve() {
  read();
  for (int i = 1; i <= n; i++) {
    for (long long bit = 0; bit <= 62; bit++) {
      if ((1LL << bit) & v[i]) {
        ans[bit].push_back(i);
      }
    }
  }
  for (int bit = 0; bit < 62; bit++) {
    if (ans[bit].size() >= 3) {
      cout << 3;
      return;
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
      if ((v[i] & v[j])) {
        gr[i].push_back(j);
        gr[j].push_back(i);
      }
    }
  }
  int MIN = inf;
  for (int i = 1; i <= n; i++) {
    MIN = min(MIN, bfs(i));
  }
  if (MIN == inf) {
    cout << -1;
  } else {
    cout << MIN;
  }
}
int main() {
  start();
  solve();
  return 0;
}
