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;
const long double pi = acos(-1.0);
const long long day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const long long digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
const long long dx[4] = {0, 1, 0, -1};
const long long dy[4] = {1, 0, -1, 0};
const long long dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const long long dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const long long dxk[8] = {-1, -2, -1, 2, -2, 1, 1, 2};
const long long dyk[8] = {-2, -1, 2, -1, 1, -2, 2, 1};
const long long alf = 26;
const long long dig = 10;
const long long two = 2;
const long long th = 3;
const long long prost = 239;
const long long bt = 30;
const long double eps = 1e-8;
const long long INF = (long long)(1e18 + 239);
const long long BIG = (1e9 + 239);
const long long MOD = 998244353;
const long long MOD2 = (long long)MOD * (long long)MOD;
mt19937 rnd(239);
const long long M = (long long)(1e5 + 239);
const long long N = (long long)(2e3 + 239);
const long long L = 18;
const long long T = (1 << 19);
const long long B = (long long)sqrt(M);
const long long X = 130;
long long n, k;
long long a[M];
vector<long long> v[X];
long long dist[X][X];
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (long long i = 0; i < n; i++) cin >> a[i];
  for (long long i = 0; i < n; i++)
    for (long long t = 0; t < 60; t++)
      if (((a[i] >> t) & 1LL) != 0 && v[t].size() <= 2) v[t].push_back(i);
  for (long long t = 0; t < 60; t++)
    if (v[t].size() > 2) {
      cout << 3;
      return 0;
    }
  vector<long long> vx;
  vector<pair<long long, long long> > rb;
  for (long long t = 0; t < 60; t++)
    if (v[t].size() == 2) {
      long long i = v[t][0];
      long long j = v[t][1];
      vx.push_back(i);
      vx.push_back(j);
      rb.push_back(make_pair(i, j));
    }
  sort(vx.begin(), vx.end());
  vx.resize(unique(vx.begin(), vx.end()) - vx.begin());
  k = vx.size();
  for (pair<long long, long long>& t : rb) {
    t.first = lower_bound(vx.begin(), vx.end(), t.first) - vx.begin();
    t.second = lower_bound(vx.begin(), vx.end(), t.second) - vx.begin();
    if (t.first > t.second) swap(t.first, t.second);
  }
  sort(rb.begin(), rb.end());
  rb.resize(unique(rb.begin(), rb.end()) - rb.begin());
  long long ans = BIG;
  for (long long ig = 0; ig < rb.size(); ig++) {
    for (long long i = 0; i < k; i++)
      for (long long j = 0; j < k; j++) dist[i][j] = BIG;
    for (long long i = 0; i < k; i++) dist[i][i] = 0;
    for (long long t = 0; t < rb.size(); t++)
      if (t != ig) {
        long long x = rb[t].first;
        long long y = rb[t].second;
        dist[x][y] = 1;
        dist[y][x] = 1;
      }
    for (long long h = 0; h < k; h++)
      for (long long i = 0; i < k; i++)
        for (long long j = 0; j < k; j++)
          dist[i][j] = min(dist[i][j], dist[i][h] + dist[h][j]);
    long long x = rb[ig].first;
    long long y = rb[ig].second;
    ans = min(ans, dist[x][y] + 1);
  }
  if (ans >= BIG) ans = -1;
  cout << ans;
  return 0;
}
