Given two arrays
A and
B each of length
N.
Find the value ∑Ni=1∑Nj=1max(Ai⊕Bj,Ai&Bj)
.
Here
⊕ and
& denote the bitwise XOR operation and bitwise AND operation respectively.
Input Format
- The first line of input contains a single integer T
- the number of test cases. The description of
T test cases follows.
The first line of each test case contains an integer N - the length of arrays
A and
B.
The second line of each test case contains N space-separated integers
A1,A2,…,AN representing the array
A.
The third line of each test case contains N space-separated integers
B1,B2,…,BN representing the array
B
Output Format
For each test case, output the value ∑Ni=1∑Nj=1max(Ai⊕Bj,Ai&Bj)
.
Constraints
1≤N≤105
0≤Ai,Bi<220
Sum of N does not exceed
2⋅105
Sample Input 1
3
2
3 4
1 2
1
0
0
3
2 4 3
1 2 1
Sample Output 1
15
0
30
Explanation
: For the given arrays, the value is:
max(3⊕1,3&1)+max(3⊕2,3&2)+max(4⊕1,4&1)+max(4⊕2,4&2)=2+2+5+6=15.
Test Case 2
: For the given arrays, the value is:
max(0⊕0,0&0)=0.
Test Case 3
: For the given arrays, the value is:
max(2⊕1,2&1)+max(2⊕2,2&2)+max(2⊕1,2&1)+max(4⊕1,4&1)+max(4⊕2,4&2)+max(4⊕1,4&1)+max(3⊕1,3&1)+max(3⊕2,3&2)+max(3⊕1,3&1)
=3+2+3+5+6+5+2+2+2=30
ConversionConversion EmoticonEmoticon