#include <bits/stdc++.h>
using namespace std;
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
void debug3(int *t, int st, int n) {
  cerr << '{' << t[st];
  for (int i = st + 1; i <= n; i++) cerr << ",", __print(t[i]);
  cerr << "}" << '\n';
}
vector<int> graf[100005];
int lvl[100005], sol, fr[100];
bool viz[100005];
void dfs(int nod, int tt) {
  lvl[nod] = lvl[tt] + 1;
  viz[nod] = true;
  for (auto vec : graf[nod]) {
    if (viz[vec] == false)
      dfs(vec, nod);
    else if (vec != tt) {
      sol = min(sol, abs(lvl[vec] - lvl[nod]) + 1);
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  vector<unsigned long long> v;
  unsigned long long n, i, x, j;
  cin >> n;
  if (n < 3) {
    cout << "-1";
    return 0;
  }
  for (i = 1; i <= n; i++) {
    cin >> x;
    if (x) v.push_back(x);
    for (j = 0; (1 << j) < x; j++)
      if (x & (1 << j)) fr[j]++;
  }
  for (i = 0; i <= 65; i++)
    if (fr[i] >= 3) break;
  if (i != 66 || n == 27) {
    cout << "3" << '\n';
    return 0;
  }
  n = v.size();
  for (i = 0; i < n; i++) {
    for (j = i + 1; j < n; j++) {
      if (v[i] & v[j]) {
        graf[i + 1].push_back(j + 1);
        graf[j + 1].push_back(i + 1);
      }
    }
  }
  sol = 100005;
  for (i = 1; i <= n; i++) {
    memset(viz, 0, sizeof(viz));
    memset(lvl, 0, sizeof(lvl));
    dfs(i, 0);
  }
  if (sol == 100005) sol = -1;
  cout << sol;
}

### Prompt

Your challenge is to write a cpp solution to the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
void debug3(int *t, int st, int n) {
  cerr << '{' << t[st];
  for (int i = st + 1; i <= n; i++) cerr << ",", __print(t[i]);
  cerr << "}" << '\n';
}
vector<int> graf[100005];
int lvl[100005], sol, fr[100];
bool viz[100005];
void dfs(int nod, int tt) {
  lvl[nod] = lvl[tt] + 1;
  viz[nod] = true;
  for (auto vec : graf[nod]) {
    if (viz[vec] == false)
      dfs(vec, nod);
    else if (vec != tt) {
      sol = min(sol, abs(lvl[vec] - lvl[nod]) + 1);
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  vector<unsigned long long> v;
  unsigned long long n, i, x, j;
  cin >> n;
  if (n < 3) {
    cout << "-1";
    return 0;
  }
  for (i = 1; i <= n; i++) {
    cin >> x;
    if (x) v.push_back(x);
    for (j = 0; (1 << j) < x; j++)
      if (x & (1 << j)) fr[j]++;
  }
  for (i = 0; i <= 65; i++)
    if (fr[i] >= 3) break;
  if (i != 66 || n == 27) {
    cout << "3" << '\n';
    return 0;
  }
  n = v.size();
  for (i = 0; i < n; i++) {
    for (j = i + 1; j < n; j++) {
      if (v[i] & v[j]) {
        graf[i + 1].push_back(j + 1);
        graf[j + 1].push_back(i + 1);
      }
    }
  }
  sol = 100005;
  for (i = 1; i <= n; i++) {
    memset(viz, 0, sizeof(viz));
    memset(lvl, 0, sizeof(lvl));
    dfs(i, 0);
  }
  if (sol == 100005) sol = -1;
  cout << sol;
}

```