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.
import sys
input = sys.stdin.readline
from collections import deque

class Graph(object):
	"""docstring for Graph"""
	def __init__(self,n,d): # Number of nodes and d is True if directed
		self.n = n
		self.graph = [[] for i in range(n)]
		self.parent = [-1 for i in range(n)]
		self.directed = d
		
	def addEdge(self,x,y):
		self.graph[x].append(y)
		if not self.directed:
			self.graph[y].append(x)

	def bfs(self, root): # NORMAL BFS
		queue = [root]
		queue = deque(queue)
		vis = [0]*self.n
		while len(queue)!=0:
			element = queue.popleft()
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i]==0:
					queue.append(i)
					self.parent[i] = element
					vis[i] = 1

	def dfs(self, root): # Iterative DFS
		ans = [0]*n
		stack=[root]
		vis=[0]*self.n
		stack2=[]
		while len(stack)!=0: # INITIAL TRAVERSAL
			element = stack.pop()
			if vis[element]:
				continue
			vis[element] = 1
			stack2.append(element)
			for i in self.graph[element]:
				if vis[i]==0:
					self.parent[i] = element
					stack.append(i)
		while len(stack2)!=0: # BACKTRACING. Modify the loop according to the question
			element = stack2.pop()
			m = 0
			for i in self.graph[element]:
				if i!=self.parent[element]:
					m += ans[i]
			ans[element] = m
		return ans

	def shortestpath(self, source, dest): # Calculate Shortest Path between two nodes
		self.bfs(source)
		path = [dest]
		while self.parent[path[-1]]!=-1:
			path.append(parent[path[-1]])
		return path[::-1]

	def detect_cycle(self):
		indeg = [0]*self.n
		for i in range(self.n):
			for j in self.graph[i]:
				indeg[j] += 1
		q = deque()
		vis = 0
		for i in range(self.n):
			if indeg[i]==0:
				q.append(i)
		while len(q)!=0:
			e = q.popleft()
			vis += 1
			for i in self.graph[e]:
				indeg[i] -= 1
				if indeg[i]==0:
					q.append(i)
		if vis!=self.n:
			return True
		return False

	def reroot(self, root, ans):
		stack = [root]
		vis = [0]*n
		while len(stack)!=0:
			e = stack[-1]
			if vis[e]:
				stack.pop()
				# Reverse_The_Change()
				continue
			vis[e] = 1
			for i in graph[e]:
				if not vis[e]:
					stack.append(i)
			if self.parent[e]==-1:
				continue
			# Change_The_Answers()

	def eulertour(self, root):
		stack=[root]
		t = []
		while len(stack)!=0:
			element = stack[-1]
			if vis[element]:
				t.append(stack.pop())
				continue
			t.append(element)
			vis[element] = 1
			for i in self.graph[element]:
				if not vis[i]:
					stack.append(i)
		return t

	def check(self, root):
		q = [root]
		q = deque(q)
		vis = [0]*self.n
		dist = {root:0}
		vis[root] = 1
		self.parent = [-1]*n
		ans = 10**18
		while q:
			e = q.popleft()
			for i in self.graph[e]:
				if i not in dist:
					dist[i] = dist[e] + 1
					self.parent[i] = e
					q.append(i)
				elif self.parent[e]!=i and self.parent[i]!=e:
					ans = min(ans, dist[e] + dist[i] + 1)
		return ans




	def cycle(self):
		ans = 10**18
		for i in range(n):
			x = self.check(i)
			ans = min(ans, x)
		return ans



n = int(input())
b = list(map(int,input().split()))
a = [b[i] for i in range(n) if b[i]!=0]
n = len(a)
if n==0:
	print (-1)
	exit()

o = []
for i in range(n):
	if a[i]%2:
		o.append(i)
if len(o)>=3:
	print (3)
	exit()

count = [0]*64
for i in a:
	x = bin(i)[2:]
	x = "0"*(64-len(x))+x
	for j in range(64):
		if x[j]=="1":
			count[j] += 1
for i in count:
	if i>=3:
		print (3)
		exit()

g = Graph(n, False)
for i in range(n):
	for j in range(i+1, n):
		if a[i]&a[j]!=0:
			g.addEdge(i, j)
			root = i
t = [0]*n
ans = g.cycle()
# print (g.graph)
if ans==10**18:
	print (-1)
else:
	print (ans)



