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;
using ll = long long;
using ull = unsigned long long;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
using tp = tuple<ll, ll, ll>;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = 998244353LL;
using ld = long double;
static const ld pi = 3.141592653589793L;
using Array = vector<ll>;
using Matrix = vector<Array>;
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
struct Edge {
  ll to, cap, rev;
  Edge(ll _to, ll _cap, ll _rev) {
    to = _to;
    cap = _cap;
    rev = _rev;
  }
};
void add_edge(vector<vector<Edge>> &G, ll from, ll to, ll cap, bool revFlag,
              ll revCap) {
  G[from].push_back(Edge(to, cap, (ll)G[to].size()));
  if (revFlag) G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}
void Dijkstra(vector<vector<Edge>> &G, ll s, Array &d) {
  d.resize(G.size());
  for (ll i = (ll)(0); i < (ll)(d.size()); ++i) d[i] = INF;
  d[s] = 0;
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
  q.push(make_pair(0, s));
  while (!q.empty()) {
    pair<ll, ll> a = q.top();
    q.pop();
    if (d[a.second] < a.first) continue;
    for (ll i = (ll)(0); i < (ll)(G[a.second].size()); ++i) {
      Edge e = G[a.second][i];
      if (d[e.to] > d[a.second] + e.cap) {
        d[e.to] = d[a.second] + e.cap;
        q.push(make_pair(d[e.to], e.to));
      }
    }
  }
}
void solve() {
  ll n;
  cin >> n;
  vec<ll> a(n);
  for (ll i = (ll)(0); i < (ll)(n); ++i) {
    cin >> a[i];
  }
  vector<vector<Edge>> g(n);
  vvec<ll> es(60);
  for (ll i = (ll)(0); i < (ll)(n); ++i) {
    for (ll j = (ll)(0); j < (ll)(60); ++j) {
      if ((a[i] >> j) & 1) {
        es[j].push_back(i);
        if (es[j].size() == 3) {
          cout << 3 << '\n';
          return;
        }
      }
    }
  }
  set<pair<ll, ll>> st;
  for (ll i = (ll)(0); i < (ll)(60); ++i) {
    if (es[i].size() == 2) {
      int u = es[i][0], v = es[i][1];
      if (st.count({u, v})) continue;
      add_edge(g, u, v, 1, true, 1);
      st.insert({u, v});
    }
  }
  ll ans = INF;
  for (ll v = (ll)(0); v < (ll)(n); ++v) {
    for (auto &e : g[v]) {
      e.cap = INF;
      Array d;
      Dijkstra(g, v, d);
      chmin(ans, d[e.to] + 1);
      e.cap = 1;
    }
  }
  if (ans == INF)
    cout << -1 << '\n';
  else
    cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  solve();
  return 0;
}
