Kakarot and Vegeta are both training their sons Goten and Trunks as only they can defeat Beerus. To train them, Kakarot lays out an undirected graph where each node is connected to every other node (even to itself). Each node also has a weight, which is hidden. The weight on node i is $node_{i}$.

For Goten, the time taken to jump from one node to another is $node_{1}$ OR $node_{2}$ (OR is the bitwise OR operator) and for Trunks it's $node_{1}$ AND $node_{2}$ (AND is the bitwise AND operator). Goten and Trunks figure out that they can fuse to become Gotenks and  become really powerful. 

But for Gotenks the time between each node is the sum of  the time taken by Goten and Trunks between each node. To test the mental ability of Gotenks, Kakarot asks him a question. He gives them two separate arrays. One for Goten(Go) and one for Trunks(Tr). 
Each array contains, the total time that person takes to go from that node to each particular node directly. For example ith index of the  array Go contains, $Go_{i}$ = ($node_{i}$ OR $node_{1}$) + ($node_{i}$ OR $node_{2}$) + ($node_{i}$ OR $node_{3}$) + ... + ($node_{i}$ OR $node_{n}$). And the ith index of the  array Tr contains, $Tr_{i}$ = ($node_{i}$ AND $node_{1}$) + ($node_{i}$ AND $node_{2}$) + ($node_{i}$ AND $node_{3}$) + ... + ($node_{i}$ AND $node_{n}$). 

After giving Gotenks these two arrays he asks him to remake that graph based on the times taken for Gotenks to travel between the nodes. That is, in the new graph, the weight of an edge (i, j) will be ($node_{i}$ OR $node_{j}$) + ($node_{i}$ AND $node_{j}$). You need to find the Maximum Spanning Tree of the graph. To pass Vegeta and Kakarot's mental ability test Gotenks must tell them the total weight of this tree. 

Help Gotenks to pass this test so that Beerus can be defeated.

------ 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 each test case contains a single integer, N denoting the size of the arrays.
The second line of each test case contains N integers denoting elements of the array Go separated by single spaces.
The third line of each test case contains N integers denoting elements of the array Tr separated by single spaces.

------ Output: ------
For each test case output in a single line, the total weight of the maximum spanning tree.

------ Constraints  ------
$1 ≤ T ≤ 2$
$2 ≤ N ≤ 10^{5}$
$1 ≤ Go_{i} ≤ 10^{9}$
$1 ≤ Tr_{i} ≤ 10^{9}$

------ Sample Input: ------
	1
	2
4 5   
5 6

------ Sample Output: ------
	5

Source: codechef | Difficulty: VERY_HARD


Solutions:
def getWts(ab):
	n = len(ab)
	s = sum(ab) // (2 * n)
	mn = min(ab)
	relwt = [(a - mn) // n for a in ab]
	dd = (s - sum(relwt)) // n
	ret = [x + dd for x in relwt]
	return ret

def sol(ab):
	n = len(ab)
	w = sorted(getWts(ab))
	return sum(w[:-1]) + w[-1] * (n - 1)
import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	f.readline()
	a = list(map(int, f.readline().split()))
	b = list(map(int, f.readline().split()))
	c = [x + y for (x, y) in zip(a, b)]
	print(sol(c))