E. XOR Subarray Minimization
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$t$$$ independent test cases. In each test case, you are given an array of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$.

You can perform the following operation at most once for each integer $$$k$$$ such that $$$2^k \le n$$$:

  • Choose a contiguous subarray of length exactly $$$2^k$$$.
  • For every element $$$a_i$$$ in that subarray, replace it with $$$a_i \leftarrow a_i \oplus 2^k$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.

Your task is to determine the minimum possible sum of the array elements after performing these operations optimally, given that for each valid $$$k$$$, the corresponding operation may be performed at most once (and possibly not at all).

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of test cases.

Each test case consists of two lines:

  • The first line contains an integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the number of elements in the array.
  • The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ $$$(0 \le a_i \lt 2^{30})$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, print a single integer — the minimum sum of the array that can be obtained after performing the operations optimally.

Example
Input
5
1
10
4
1 5 4 5
5
9 4 9 5 2
2
3 3
1
3
Output
10
6
28
1
2