You are given an array $a$ of size $n$.

You can perform the following operation on the array:

Choose two different integers $i, j$ $(1 \leq i < j \leq n$), replace $a_i$ with $x$ and $a_j$ with $y$. In order not to break the array, $a_i | a_j = x | y$ must be held, where $|$ denotes the bitwise OR operation . Notice that $x$ and $y$ are non-negative integers.

Please output the minimum sum of the array you can get after using the operation above any number of times.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ $(1 \leq t \leq 1000)$. Description of the test cases follows.

The first line of each test case contains an integer $n$ $(2 \leq n \leq 100)$ — the size of array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots ,a_n$ $(0 \leq a_i < 2^{30})$.


-----Output-----

For each test case, print one number in a line — the minimum possible sum of the array.


-----Examples-----

Input
4
3
1 3 2
5
1 2 4 8 16
2
6 6
3
3 5 6
Output
3
31
6
7


-----Note-----

In the first example, you can perform the following operations to obtain the array $[1, 0, 2]$:

1. choose $i = 1, j = 2$, change $a_1 = 1$ and $a_2 = 2$, it's valid since $1 | 3 = 1 | 2$. The array becomes $[1, 2, 2]$.

2. choose $i = 2, j = 3$, change $a_2 = 0$ and $a_3 = 2$, it's valid since $2 | 2 = 0 | 2$. The array becomes $[1, 0, 2]$.

We can prove that the minimum sum is $1 + 0 + 2 = 3$

In the second example, We don't need any operations.

Difficulty: EASY
Tags: Bit manipulation

Greedy algorithms
Skill types: Bit manipulation

Greedy algorithms

Starter code:

Solutions:
for s in [*open(0)][2::2]:
	x = 0
	print([(x := (x | int(i))) for i in s.split()][-1])


for a in [*open(0)][2::2]:
	ans = 0
	for i in [*map(int, a.split())]:
		ans = ans | i
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	bit = 0
	for i in a:
		bit = bit | i
	print(bit)


n = int(input())
arr = [[]] * n
i = 0
while n:
	y = int(input())
	x = list(map(int, input().split()))
	arr[i] = x
	i += 1
	n -= 1

def cal(arr):
	res = 0
	for num in arr:
		res = res | num
	print(res)
for a in arr:
	cal(a)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	n = inp()
	a = lis()
	x = 0
	for i in a:
		x = x | i
	print(x)


import sys

def input():
	return sys.stdin.readline()[:-1]

def readline():
	return map(int, input().split())

def solve():
	(n,) = readline()
	a = readline()
	r = 0
	for ai in a:
		r |= ai
	print(r)
t = int(input())
for __ in range(t):
	solve()


import math

def Solve():
	n = int(input())
	a = list(map(int, input().split()))
	s = a[0] | a[1]
	for i in range(1, n):
		s = s | a[i]
	print(s)
q = int(input())
while q > 0:
	Solve()
	q = q - 1


import sys
input = sys.stdin.readline

def solve(n, arr):
	ans = 0
	for num in arr:
		ans = ans | num
	print(ans)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	solve(n, arr)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	res = lst[0] | lst[1]
	for i in range(2, n):
		res = res | lst[i]
	print(res)


for s in [*open(0)][2::2]:
	r = 0
	for x in s.split():
		r |= int(x)
	print(r)


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for x in arr:
		ans = ans | x
	return ans
for _ in range(int(input())):
	print(main())


def fun():
	n = int(input())
	arr = list(map(int, input().split()))
	res = 0
	for i in arr:
		res |= i
	return res
for _ in range(int(input())):
	print(fun())


out = []
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	ans = a[0]
	for i in a:
		ans |= i
	out.append(ans)
for i in out:
	print(i)


t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = 0
	for el in a:
		x = x | el
	print(x)


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for aa in a:
		ans |= aa
	print(ans)


def solve(a):
	s = 0
	for el in a:
		s = s | el
	return s
out = []
t = int(input())
for case in range(t):
	s = input()
	a = list(map(int, input().split(' ')))
	out.append(str(solve(a)))
print('\n'.join(out))


for i in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	z = 0
	for p in range(0, x):
		z = z | l[p]
	print(z)


def min_sum(aa):
	all_bits = 0
	for x in aa:
		all_bits = all_bits | x
	return all_bits
n_t = int(input())
for t in range(n_t):
	n = int(input())
	aa = list(map(int, input().split(' ')))
	assert len(aa) == n
	result = min_sum(aa)
	print(result)


for t in range(int(input())):
	size = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for n in a:
		ans |= n
	print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	answer = 0
	for num in arr:
		answer |= num
	print(answer)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in a:
		ans |= i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	ct = 0
	for num in a:
		ct |= num
	print(ct)


for s in [*open(0)][2::2]:
	x = 0
	for n in map(int, s.split()):
		x |= n
	print(x)


in1 = lambda : int(input())
in2 = lambda : list(map(int, input().split()))
inf = 10 ** 20
mod = 998244353

def main():
	for _ in range(in1()):
		N = in1()
		A = in2()
		ans = 0
		for v in A:
			ans |= v
		print(ans)
main()


for x in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for x in a:
		ans |= x
	print(ans)


for _ in range(int(input())):
	N = int(input())
	l1 = list(map(int, input().split()))
	sum1 = l1[0] | l1[1]
	for i in range(2, N):
		sum1 = sum1 | l1[i]
	print(sum1)


import sys
import math
from collections import deque, defaultdict
input = sys.stdin.readline

def multiple():
	a = map(int, input().split())
	return a

def array():
	a = input().split()
	return a

def intarray():
	a = list(map(int, input().split()))
	return a

def solution():
	n = int(input())
	s = intarray()
	ans = 0
	for i in s:
		ans = ans | i
	print(ans)
	return
t = int(input())
for _ in range(t):
	solution()


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = a[0]
	for i in range(1, len(a)):
		x |= a[i]
	print(x)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans |= a[i]
	print(ans)
tst = int(input())
for i in range(tst):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	x = 0
	for i in s:
		x = x | i
	print(x)


def solve(l, n):
	sum = 0
	for i in l:
		sum = sum | i
	return sum
t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	l = list(map(int, input().split()))
	print(solve(l, n))


for i in range(int(input())):
	lenn = int(input())
	list1 = list(map(int, input().split()))
	count = 0
	for i in range(lenn):
		count = count | list1[i]
	print(count)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	for j in range(n):
		s = s | a[j]
	print(s)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = a[0] | a[1]
	for i in range(2, n):
		s = s | a[i]
	print(s)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = list(map(int, input().split()))
	x = 0
	for i in range(n):
		x = x | s[i]
	print(x)


loopcount = int(input())
for loop in range(loopcount):
	a = int(input())
	x = input()
	x = x.split(' ')
	x = list(map(int, x))
	output = 0
	for i in x:
		output = output | i
	print(output)


def find(arr):
	result = arr[0]
	for i in range(1, len(arr)):
		result = result | arr[i]
	return result
num = int(input())
for i in range(num):
	n = input()
	arr = [int(x) for x in input().split()]
	a = find(arr)
	print(a)


for i in range(int(input())):
	n = int(input())
	a = [int(I) for I in input().split()]
	answer = a[0]
	for I in a[1:]:
		answer = answer | I
	print(answer)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for num in arr:
		ans |= num
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = a[0] | a[1]
	i = 2
	while i < n:
		ans = ans | a[i]
		i += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p = 0
	for i in range(n):
		p = p | l[i]
	print(p)


def solve():
	tests = int(input())
	for _ in range(tests):
		numb = int(input())
		arr = list(map(int, input().split(' ')))
		numb = arr[0]
		for i in range(1, len(arr)):
			numb = numb | arr[i]
		print(numb)
solve()


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(len(arr)):
		ans = ans | arr[i]
	print(ans)


def func(arr):
	ans = 0
	for i in arr:
		ans = ans | i
	return ans
n = int(input())
while n > 0:
	t = int(input())
	arr = list(map(int, input().split()))
	print(func(arr))
	n -= 1


for i in range(0, int(input())):
	n = int(input())
	v = list(map(int, input().split()))
	x = 0
	for i in v:
		x |= i
	print(x)


t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	summ = arr[0] | arr[1]
	list1 = []
	for i in range(2, len(arr)):
		summ = summ | arr[i]
	print(summ)


t = int(input())
for tt in range(t):
	n = int(input())
	s = input().split()
	a = [int(i) for i in s]
	res = a[0]
	for i in range(1, n):
		res |= a[i]
	print(res)


t = int(input())
for i in range(0, t):
	n = int(input())
	arr = list(map(int, input().split()))
	res = 0
	for i in arr:
		res = res | i
	print(res)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = l[0]
	for x in l:
		c |= x
	print(c)


N = int(input())
inputs = []
for i in range(N):
	elm = int(input())
	arr = list(map(int, input().split()))
	inputs.append(arr)
ans = []
for arr in inputs:
	x = arr[0]
	for elm in arr:
		x |= elm
	ans.append(x)
for elm in ans:
	print(elm)


for _ in range(int(input())):
	(_, arr) = (input(), list(map(int, input().split())))
	x = arr[0]
	for y in arr:
		x |= y
	print(x)


import math
n = int(input())
for i in range(n):
	tam = int(input())
	lista = list(map(int, input().split()))
	dicio = {}
	soma = 0
	for item in lista:
		soma = soma | item
	print(soma)


testcase = int(input())
for x in range(testcase):
	wastenumber = int(input())
	wastenumber = x
	lsto = list(map(int, input().split()))
	result = 0
	for j in lsto:
		result |= j
	print(result)


import sys
import math

def mp():
	return map(int, sys.stdin.readline().split())

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

def main(tc: int):
	n = ri()
	a = ria()
	s = 0
	for i in a:
		s |= i
	ans = 0
	cnt = 0
	while s:
		if s & 1:
			ans += 2 ** cnt
			cnt += 1
		else:
			cnt += 1
		s >>= 1
	wi(ans)
t = ri()
for tc in range(1, t + 1):
	main(tc)


import sys
from math import *
from functools import *
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = a[0]
	for i in a:
		ans |= i
	print(ans)


for _ in range(int(input())):
	(n, x) = (input(), 0)
	for i in map(int, input().split()):
		x |= i
	print(x)


for _ in range(int(input())):
	bool = True
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for ele in l:
		ans |= ele
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	ans = 0
	inp = [int(XXX) for XXX in input().split()]
	ans = 0
	for XXX in inp:
		ans = ans | XXX
	print(ans)


import sys
import heapq
from math import gcd
input = lambda : sys.stdin.readline().rstrip()

def main():
	for _ in range(int(input())):
		n = int(input())
		arr = [int(item) for item in input().split()]
		for i in range(len(arr) - 1):
			arr[i + 1] = arr[i] | arr[i + 1]
		print(arr[-1])
main()


for _ in range(int(input())):
	(n, a) = (int(input()), map(int, input().split()))
	ans = 0
	for num in a:
		ans |= num
	print(ans)


t = int(input())
for i in range(t):
	tc = int(input())
	inp = list(map(int, input().split()))
	findex = inp[0]
	for j in range(1, tc):
		findex = findex | inp[j]
	print(findex)


def solve(arr):
	res = 0
	for i in arr:
		res |= i
	return res

def main():
	t = int(input())
	res = []
	for _ in range(t):
		n = input()
		arr = list(map(int, input().split()))
		res.append(solve(arr))
	for _ in res:
		print(_)
main()


t = int(input())
while t:
	n = int(input())
	arr = [int(x) for x in input().split()]
	sumn = arr[0]
	for i in range(1, len(arr)):
		sumn = sumn | arr[i]
	print(sumn)
	t -= 1


from math import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from collections import Counter as ctr
from collections import deque as dq
from array import array
inp = lambda : int(input())
li = lambda : list(map(int, input().split()))
lb = lambda : list(map(int, input()))
ls = lambda : list(input())
bi = lambda n: bin(n).replace('0b', '')
yn = lambda f: print('NYOE S'[f::2])

def solve(__=1):
	for _ in range(__):
		n = inp()
		a = li()
		ans = 0
		for x in a:
			ans |= x
		print(ans)
solve(inp())


mod = 10000000
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	for i in range(n):
		s = s | a[i]
	print(s)


t = int(input())
for i in range(t):
	a = int(input())
	x = list(map(int, input().split()))
	s = 0
	for j in range(len(x)):
		s = s | x[j]
	print(s)


def solve(arr):
	summ = 0
	for num in arr:
		summ |= num
	return summ
t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(arr))
	t -= 1


for _ in range(int(input())):
	input()
	s = list(map(int, input().split()))
	ans = 0
	for i in s:
		ans |= i
	print(ans)


for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	b = 0
	for i in l:
		b = b | i
	print(b)


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	ans = arr[0]
	for i in arr:
		ans = ans | i
	print(ans)
	t -= 1


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	res = 0
	for i in range(N):
		res |= A[i]
	print(res)


t = int(input())
for batch in range(t):
	n = int(input())
	row = list(map(int, input().split()))
	ans = 0
	for i in range(len(row)):
		ans = ans | row[i]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = a[0]
	for i in a[1:]:
		count = count | i
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	m = 0
	for i in lst:
		m = m | i
	print(m)


def solve():
	N = int(input())
	array = list(map(int, input().split()))
	output = 0
	for i in range(N):
		output = output | array[i]
	return output
remained_test_cases = 1
remained_test_cases = int(input())
while remained_test_cases > 0:
	print(solve())
	remained_test_cases -= 1


t = int(input())
for _ in range(t):
	N = int(input())
	given_arr = list(map(int, input().split()))
	ans = 0
	for i in range(N):
		ans |= given_arr[i]
	print(ans)


res = []
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	r = 0
	for x in a:
		r = r | x
	res.append(r)
for i in res:
	print(i)


for i in range(int(input())):
	input1 = int(input())
	input2 = list(map(int, input().split()))
	res = 0
	for i in input2:
		res = res | i
	print(res)


import math
t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	Or = 0
	for i in range(n):
		Or = Or | arr[i]
	print(Or)


for _ in range(int(input())):
	n = int(input())
	s = 0
	for a in map(int, input().split()):
		s = s | a
	print(s)


def solve(nums):
	mask = nums[0]
	sum_ = nums[0]
	for n in nums[1:]:
		n_ = n & ~mask
		mask |= n_
		sum_ += n_
	return sum_
T = int(input())
for _ in range(T):
	n = int(input())
	nums = [int(x) for x in input().split()]
	print(solve(nums))


for i in range(int(input())):
	ab = int(input())
	abc = list(map(int, input().split()))
	x = abc[0] | abc[1]
	for i in range(2, len(abc)):
		x |= abc[i]
	print(x)


t = int(input())
for _ in range(0, t):
	n = int(input())
	list1 = [int(num) for num in input().split()]
	i = 0
	num = 0
	for i in range(0, len(list1)):
		num = num | list1[i]
	print(num)


t = int(input())
while t:
	t -= 1
	n = int(input())
	l = list(map(int, input().strip().split()))[:n]
	bitor = 0
	for i in range(0, len(l)):
		bitor = bitor | l[i]
	print(bitor)