XOR-AND Coupling

Shuvo_Malakar Criterion 2022 Round 17
Limits 1s, 512 MB

You are given an array AA of NN positive integers A1,A2,..,AN1,ANA_1, A_2, ………..,A_{N-1}, A_N which are some powers of 22. You have to do the following operations on the array-

  1. Divide the array into KK(1KN)( 1 \le K \le N ) groups. Each group should contain at least one element. And each element of the array should occur in exactly one group.

  2. The summation of bitwise AND of the elements of each group is minimum.

Find the maximum possible summation of bitwise XOR of the elements of each group so that all the above conditions are satisfied.

For example, given an array: [4,8,16,2,2][4,8,16,2,2], we can divide it into two groups [2,4][ 2, 4 ]and [2,8,16][ 2, 8, 16 ]. So, the summation of bitwise AND is (2(2 &\& 4)4) ++ (2(2 &\& 88 &\& 16)16) =0+0=0= 0 + 0 = 0, which is minimum possible and the summation of bitwise XOR is (24)+(2816)=6+26=32(2 \oplus 4) + (2 \oplus 8 \oplus 16) = 6 + 26 = 32, which is maximum possible. So, the answer is 3232.

Now write a program to calculate the answer.

Input

The first line of the input contains a single integer TT(1T5×105)( 1\le T \le 5\times 10^5 )-the number of test cases.

Each test case consists of two lines. The first line of each test case contains an integer NN(1N5×105)( 1 \le N \le 5 \times 10^5 )-the number of the elements of the array AA. The next line contains NN integers. The ithi^{th}(1iN)( 1 \le i \le N ) integer is a positive integer AiA_i, which is some power of two, 2k2^k(0k30)( 0 \le k \le 30 ).

Sum of NN over all test cases doesn’t exceed 5×1055\times10^5.

Output

For each test case print a single integer in a single line which is the answer of the test case.

Sample

InputOutput
3
5
4 8 16 2 2
6
4 8 4 32 16 8
7
2 2 2 2 4 16 64
32
72
88

Submit

Login to submit.

Statistics

43% Solution Ratio
NirjhorEarliest, 1M ago
AlfehsaniFastest, 0.0s
NirjhorLightest, 3.1 MB
serotoninShortest, 720B
Toph uses cookies. By continuing you agree to our Cookie Policy.