You are given a sequence of non-negative integers $A_1, A_2, \ldots, A_N$. At most once, you may choose a non-negative integer $X$ and for each valid $i$, change $A_i$ to $A_i \oplus X$ ($\oplus$ denotes bitwise XOR).
Find the minimum possible value of the sum of all elements of the resulting sequence.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of the input contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer ― the minimum possible sum.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le N \le 10^5$
- $1 \le A_i \le 10^9$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (50 points):
- $1 \le N \le 10^3$
- $1 \le A_i \le 10^3$ for each valid $i$
Subtask #2 (50 points): original constraints

-----Example Input-----
3
5
2 3 4 5 6
4
7 7 7 7
3
1 1 3

-----Example Output-----
14
0
2

-----Explanation-----
Example case 1: If we choose $X = 6$, the sequence becomes $(4, 5, 2, 3, 0)$.
Example case 2: We can choose $X = 7$ to make all elements of the resulting sequence equal to $0$.
Example case 3: We can choose $X = 1$. The sequence becomes $(0, 0, 2)$, with sum $2$.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
# cook your dish here
test=int(input())
for _ in range(test):
 n=int(input())
 a=[(bin(int(x))[2:][::-1]+("0")*32)for x in input().split()]
 res=""
 mysum=0
 for i in range(32):
  mycount=0
  for j in range(n):
   if(a[j][i]=="0"):
    mycount+=1
  if(mycount==n):
   break
  if(mycount>(n//2)):
   res+="0"
   mysum+=(n-mycount)*int(pow(2,i))
  else:
   res+="1"
   mysum+=mycount*int(pow(2,i))
 print(mysum)

# cook your dish here
test=int(input())
for _ in range(test):
 n=int(input())
 a=[(bin(int(x))[2:][::-1]+("0")*32)for x in input().split()]
 res=""
 mysum=0
 for i in range(32):
  mycount=0
  for j in range(n):
   if(a[j][i]=="0"):
    mycount+=1
  if(mycount==n):
   break
  if(mycount>(n//2)):
   res+="0"
   mysum+=(n-mycount)*int(pow(2,i))
  else:
   res+="1"
   mysum+=mycount*int(pow(2,i))
 print(mysum)

t = int(input())
for _ in range(t):
 n = int(input())
 a = [(bin(int(x))[2:][::-1]+("0")*32)for x in input().split()]
 res = ""
 mysum = 0
 for i in range(32):
  mycount = 0
  for j in range(n):
   if(a[j][i] == "0"):
    mycount += 1
  if(mycount == n):
   break
  if(mycount > (n//2)):
   res += "0"
   mysum += (n-mycount)*int(pow(2,i))
  else:
   res += "1"
   mysum += mycount*int(pow(2,i))
 print(mysum)

import operator
t=int(input())
for z in range(t):
  n=int(input())
  lis=list(map(int,input().split()))
  lis2=[0]*32
  for i in range(n):
    a=bin(lis[i])[2:]
    for i in range(len(a)):
      if a[i]=='1':
        lis2[len(a)-i-1]+=1
  ss=''
  lis2.reverse()
  #print(lis2)
  for i in lis2:
    if i>n//2:
      ss+='1'
    else:
      ss+='0'
  #print(ss)
  aa=int(ss,2)
  s=0
  for i in lis:
    s+=i^aa
  print(s)


import operator
t=int(input())
for z in range(t):
  n=int(input())
  lis=list(map(int,input().split()))
  lis2=[0]*32
  for i in range(n):
    a=bin(lis[i])[2:]
    for i in range(len(a)):
      if a[i]=='1':
        lis2[len(a)-i-1]+=1
  ss=''
  lis2.reverse()
  #print(lis2)
  for i in lis2:
    if i>n//2:
      ss+='1'
    else:
      ss+='0'
  #print(ss)
  aa=int(ss,2)
  s=0
  for i in lis:
    s+=i^aa
  print(s)


t = int(input())
for _ in range(t):
 n = int(input())
 l = list(map(int,input().split()))
 #print(l)
 
 s = max(l)
 s = bin(s)
 maxbits = len(s)-1
 x = []
 for i in range(maxbits+1):
  count = 0
  for j in range(n):
   if ((2**i)&l[j])==2**i:
    count+=1 
  
  
   
  if count>n//2:
   x.append(1)
  else:
   x.append(0)
 x.reverse() 
 ans = ''
 
 for i in x:
  ans+=str(i)
 ans1 = int(ans,2)
 #print(ans1)
 sm=0
 for i in l:
  sm+=(i^ans1)
 print(sm)
  
 


# cook your dish here
from math import log2
t=int(input())
def odd(a,n):
 count=0
 for i in range(n):
  count+=a[i]%2
 if count>=n/2:
  return 1;
 return 0
def divide(a):
 for i in range(len(a)):
  a[i]=a[i]>>1
 return a;
for _ in range(t):
 n=int(input())
 a=list(map(int,input().split()))
 m=a[:]
 time=int(log2(max(a))+1)
 
 i=0
 answer=0
 while i<time:
  answer+=odd(a,n)*(1<<i)
  a=divide(a)
  i+=1
  
 x=answer;
 # print(x)
 for i in range(n):
  m[i]=m[i]^x
 # print(a)
 print(sum(m)) 


from math import log2 

def findX(arr, n): 
 itr = arr[0] 
 for i in range(len(arr)): 
  if(arr[i] > itr): 
   itr = arr[i] 
 p = int(log2(itr)) + 1
 X = 0
 for i in range(p): 
  count = 0
  for j in range(n): 
   if (arr[j] & (1 << i)): 
    count += 1
  if (count > int(n / 2)): 
   X += 1 << i 
 sum = 0
 for i in range(n): 
  sum += (X ^ arr[i]) 
 print(sum)
try:
 t = int(input())
 for _ in range(t):
  ss = int(input())
  arr = list(map(int, input().split()))
  n = len(arr) 
  findX(arr, n)
except:
 pass

# # cook your dish here
# def more_frequent_item(lst):
#     new_lst = []
#     times = 0
#     for item in lst:
#         count_num = lst.count(item)
#         new_lst.append(count_num)
#         times = max(new_lst)
#     key = max(lst, key=lst.count)
#     return [key, times]
# try:
#     t = int(input())
#     for _ in range(t):
#         jk = int(input())
#         lst = list(map(int, input().split()))
#         Nlst = [0]*len(lst)
#         Nlst2 = [0]*len(lst)
#         z = more_frequent_item(lst)
#         if z[0] * z[1] > max(lst):
#             x = z[0]
#         else:
#             x = max(lst)
#         for i in range(len(lst)):
#             Nlst[i] = lst[i] ^ x
#         for j in range(len(lst)):
#             Nlst2[j] = lst[j] ^ z[0]
#         print(min(sum(Nlst), sum(Nlst2)))
# except:
#     pass4

from math import log2 
def findX(arr, n): 
 itr = arr[0] 
 for i in range(len(arr)): 
  if(arr[i] > itr): 
   itr = arr[i] 
 p = int(log2(itr)) + 1
 X = 0
 for i in range(p): 
  count = 0
  for j in range(n): 
   if (arr[j] & (1 << i)): 
    count += 1
  if (count > int(n / 2)): 
   X += 1 << i 
 sum = 0
 for i in range(n): 
  sum += (X ^ arr[i]) 
 print(sum)
def __starting_point(): 
 t = int(input())
 for _ in range(t):
  ss = int(input())
  arr = list(map(int, input().split()))
  n = len(arr) 
  findX(arr, n)
__starting_point()

# cook your dish here
tc=int(input())

while tc>0:
 n = int(input())
 sum=[]
 s=0
 lis = list(map(int, input().split()))

 for i in range(n):
  x=lis[i]
  s=0
  for j in range(n):
   y=lis[j]
   s+=y^x
  sum.append(s)
 print(min(sum))
 tc-=1

def fun(s):
 su=0
 for j,i in enumerate(s):
  if i=='1':
   su+=2**j
 return su
for i in range(int(input())):
 n=int(input())
 b=list(map(int,input().split()))
 a=list(str(bin(int(i)))[2:] for i in b)
 m=str(bin(max(b))[2:])
 l=len(m)
 s=''
 for i in range(l):
  c1=c2=0
  for j in a:
   l1=len(j)
   if l1-i-1>=0:
    if j[l1-i-1]=='0':
     c1+=1
    else:
     c2+=1
   else:
    c1+=1
  if c1>c2:
   s+='0'
  else:
   s+='1'
 s=fun(s)
 su=0
 for i in b:
  su+=s^i
 print(su)
    


# cook your dish here
for _ in range(int(input())):
 n = int(input())
 arr = list(map(int, input().split()))
 x, cur_bit = 0, 0 #max bit is the highest value bit (0-indexed)
 bitset = {}
 for ele in arr:
  while ele:
   if ele & 1: bitset[cur_bit] = bitset.get(cur_bit,0)+1
   cur_bit += 1
   ele >>= 1
  cur_bit = 0
 for b in bitset:
  if bitset[b] > n-bitset[b]: x |= (1 << b)
 total = 0
 for ele in arr: total += ele^x
 print(total)


# cook your dish here
for _ in range(int(input())):
 n = int(input())
 arr = list(map(int, input().split()))
 x, max_bit = 0, 0 #max bit is the highest value bit (0-indexed)
 bitset = {}
 for ele in arr:
  for i, bit in enumerate(reversed(bin(ele)[2:])):
   if bit == '1':
    bitset[i] = bitset.get(i,0)+1
   max_bit = max(max_bit, i)
 for b in range(max_bit+1):
  if b in bitset:
   if bitset[b] > n-bitset[b]: x |= (1 << b)
 total = 0
 for ele in arr: total += ele^x
 print(total)


# import sys

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

t = int(input())

for _ in range(t):
 n = int(input())
 ar = [int(num) for num in input().split()]

 res = 0
 for i in range(31):
  one = zero = 0

  for ele in ar:
   if ele & (1 << i):
    one += 1
   else:
    zero += 1

  if one > zero:
   res += zero * (1 << i)
  else:
   res += one * (1 << i)

 print(res)




# import sys

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

t = int(input())

for _ in range(t):
 n = int(input())
 ar = [int(num) for num in input().split()]

 res = 0
 for i in range(31):
  one = zero = 0
  x = 1

  for j in range(n):
   if ar[j] & (x << i):
    one += 1
   else:
    zero += 1

  if one > zero:
   res += zero * (x << i)
  else:
   res += one * (x << i)

 print(res)




# cook your dish here
for _ in range(int(input())):
 N = int(input())
 A = list(map(int, input().split()))
 bitCountOne=[0]*31
 bitCountZero=[0]*31
 for a in A:
  binA=bin(a)[2:][::-1]
  placeValue=-1
  for bit in binA:
   if bit=='1':
    bitCountOne[placeValue]+=1
   else:
    bitCountZero[placeValue]+=1
   placeValue-=1

 binStr=''
 for i in range(31):
  if bitCountOne[i]>bitCountZero[i]:
   binStr+='1'
  else:
   binStr+='0'

 X=int(binStr, 2)
 minSum=0
 for a in A:
  minSum+=X^a
 print(minSum)


for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 ans=0
 for i in range(32):
  c=0
  for x in l:
   if x&(1<<i):
    c+=1
  if c>n//2:
   ans|=1<<i
 x=0
 for i in l:
  x+=i^ans 
 print(x)


t=int(input())
while (t>0):
 n=int(input())
 x=list(map(int,input().split()))
 max=[]
 for i in x:
  li=[]
  for j in x:
   li.append(i^j)
  max.append(sum(li))
 print(min(max))
 t=t-1




twopow = {}
for i in range(31):twopow[i] = 2**i
for _ in range(int(input())):
 n,a,b,original_tot = int(input()),list(map(int, input().split())),dict(),0
 for i in range(31):b[i] = 0
 for i in range(n):
  s = bin(a[i])[2:][::-1];
  original_tot += a[i]
  for i in range(len(s)):
   if s[i] == '1':b[i] += 1
 change = 0
 for x in b:
  p = b[x]
  if p > 0:
   if p > n - p:change += (p - (n - p)) * (twopow[x])

 original_tot -= change
 print(original_tot)




twopow = {}
for i in range(31):twopow[i] = 2**i
for _ in range(int(input())):
 n = int(input());a = list(map(int, input().split()));b = dict()
 for i in range(31):b[i] = 0
 original_tot = 0
 for i in range(n):
  s = bin(a[i])[2:];s = s[::-1];original_tot += a[i]
  for i in range(len(s)):
   if s[i] == '1':b[i] += 1
 change = 0
 for x in b:
  p = b[x]
  if p > 0:
   if p > n - p:change += (p - (n - p)) * (twopow[x])

 original_tot -= change
 print(original_tot)




def solve():
 twopow = {}
 for i in range(31):twopow[i] = 2**i
 for _ in range(int(input())):
  n = int(input())
  a = list(map(int, input().split()))
  b = dict()
  for i in range(31):b[i] = 0
  original_tot = 0
  for i in range(n):
   s = bin(a[i])[2:]
   s = s[::-1]
   original_tot += a[i]
   for i in range(len(s)):
    if s[i] == '1':
     b[i] += 1
  change = 0
  for x in b:
   p = b[x]
   if p > 0:
    if p > n - p:
     change += (p - (n - p)) * (twopow[x])

  original_tot -= change
  print(original_tot)

solve()



# cook your dish here
T=int(input())
for i in range(T):
 n=int(input())
 a=list(map(int,input().split()))
 #k=a[0]
 
 s=sum(a)*sum(a)
 for j in range(n):
  q=0
  k=a[j]
  for t in range(n):
   q=q+(k^a[t])
   
  s=min(q,s) 
  
 print(s) 
  
  


# cook your dish here
T=int(input())
for i in range(T):
 n=int(input())
 a=list(map(int,input().split()))
 #k=a[0]
 
 s=sum(a)
 for j in range(n):
  q=0
  k=a[j]
  for t in range(n):
   q=q+(k^a[t])
   
  s=min(q,s) 
  
 print(s)