The country of Berland initially has N isolated cities, the i-th city has a significance of A_{i}. The President of Berland wants to connect all the cities. He can construct a bidirectional road of length L (L > 0) from city X to city Y if (A_{X} \& A_{Y} \& L) = L, where \& represents the [bitwise AND] operator. 

What is the minimum total length of roads he has to construct, in order to connect all the cities in Berland? Print -1 if it is impossible.

Note: City X and City Y are said to be connected if there exists a sequence of cities C_{1}, C_{2}, \ldots, C_{K} (K ≥ 1) such that C_{1} = X, C_{K} = Y, and there exists a road from C_{i} to C_{i+1}, (1 ≤ i < K). All the cities in Berland are said to be connected when every pair of cities in Berland are connected.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains N — the number of cities.
- The second line contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} — the significance of each of the N cities. 

------ Output Format ------ 

For each test case, output on a new line the minimum total length of roads to connect all the cities in Berland, or -1 if it is impossible.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $3 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
4
4 4 4 4
3
2 4 6
----- Sample Output 1 ------ 
12
6

----- explanation 1 ------ 
Test case 1: The following roads with minimum total length can be constructed to connect Berland:
- A road with $L=4$ between city $1$ and city $2$, since ($A_{1} \& A_{2} \& 4) = 4$.
- A road with $L=4$ between city $2$ and city $3$, since ($A_{2} \& A_{3} \& 4) = 4$.
- A road with $L=4$ between city $3$ and city $4$, since ($A_{3} \& A_{4} \& 4) = 4$.

Test case 2: The following roads with minimum total length can be constructed to connect Berland:
- A road with $L=2$ between city $1$ and city $3$, since ($A_{1} \& A_{3} \& 2) = 2$.
- A road with $L=4$ between city $2$ and city $3$, since ($A_{2} \& A_{3} \& 4) = 4$.

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Greedy algorithms

Tree algorithms

Spanning trees

Data structures


Solutions:
import sys, math, heapq, bisect, random, itertools
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
ints = lambda : list(map(int, input().split()))
p = 10 ** 9 + 7
inf = 10 ** 20 + 7
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p2 = [1]
for i in range(40):
	p2.append(p2[-1] * 2)
for t in range(int(input())):
	n = int(input())
	a = ints()
	if a.count(0):
		if n == 1:
			print(0)
		else:
			print(-1)
		continue
	store = [[] for i in range(32)]
	for x in range(n):
		for i in range(32):
			if a[x] & p2[i]:
				store[i].append(x)
	done = set()
	bitset = set()
	ans = 0
	for i in range(32):
		if store[i]:
			bitset.add(i)
			queue = store[i]
			done = set(store[i])
			ans += p2[i] * (len(store[i]) - 1)
			break
	bits = set()
	for i in queue:
		for j in range(32):
			if a[i] & p2[j]:
				if j not in bitset:
					bitset.add(j)
					bits.add(j)
	b = sorted(bits)
	heapq.heapify(b)
	while b:
		x = heapq.heappop(b)
		while store[x]:
			i = store[x].pop()
			if i not in done:
				heapq.heappush(b, x)
				done.add(i)
				m = x
				for j in range(32):
					if p2[j] & a[i]:
						if j in bitset:
							m = min(m, j)
						else:
							bitset.add(j)
							heapq.heappush(b, j)
				ans += p2[m]
				break
	if len(done) == n:
		print(ans)
	else:
		print(-1)