M. Xaleid scopiX
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
"A white world with white towers lined up, '7sRef'. This is the place where all colors return."

Ris, the administrator of the Prism Area, has regained her memories and power. However, to reconstruct the world that was once on the verge of collapse, she needs to stabilize the "Kaleidoscope" — the core system that connects all seven worlds.

The Kaleidoscope is built from $$$n$$$ memory fragments. Each fragment $$$i$$$ possesses a unique energy signature represented by a non-negative integer $$$a_i$$$.

In the world of 7sRef, connections between fragments are formed based on "resonance." Two distinct fragments $$$i$$$ and $$$j$$$ are connected by a bond (an undirected edge) if and only if their energy signatures share at least one common "color". Mathematically, this means the bitwise AND of their values is non-zero: $$$$$$a_i \ \& \ a_j \neq 0$$$$$$

To activate the Kaleidoscope, Acid (Ris's partner) needs to find a closed loop of resonance within these fragments. Specifically, she needs to find the smallest cycle in this graph formed by the fragments and their connections.

Mofusigil decided to help Acid calculate the length of the shortest cycle (the number of edges in the cycle). If no cycle exists in the graph, output $$$-1$$$. However, Mofusigil's ability is limited and he could not calculate the result, so this important task is handed over to you.

Input

The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^6)$$$, denoting the number of memory fragments.

The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ $$$(0 \le a_i \le 10^{18})$$$, representing the energy signature of each fragment.

Output

Output a single integer representing the length of the smallest cycle of the graph. If the graph contains no cycles, output $$$-1$$$.

Example
Input
3
3 5 6
Output
3
Note

Explanation for Sample 1:

The binary representations are:

$$$a_1 = 3_{(10)} = 011_{(2)}$$$

$$$a_2 = 5_{(10)} = 101_{(2)}$$$

$$$a_3 = 6_{(10)} = 110_{(2)}$$$

Connections:

$$$a_1 \ \& \ a_2 = 1 \neq 0$$$ (Edge $$$1-2$$$)

$$$a_2 \ \& \ a_3 = 4 \neq 0$$$ (Edge $$$2-3$$$)

$$$a_3 \ \& \ a_1 = 2 \neq 0$$$ (Edge $$$3-1$$$)

This forms a triangle (cycle of length 3).