G. 1 2 3 and XOR, Where Did Everybody Go?
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a sequence $$$a$$$ consisting of $$$n$$$ non-negative integers.

Given a sequence $$$b$$$ consisting of $$$k$$$ non-negative integers, define a dot increment on $$$b$$$ as the following operation:

  • Select an index $$$i$$$ ($$$1 \le i \le k$$$), and add any non-negative integer of choice to $$$b_i$$$.

Then, let $$$f(b)$$$ be the minimum value of $$$b_1 \oplus b_2 \oplus \ldots \oplus b_k$$$ after performing a dot increment on $$$b$$$ exactly once.$$$^{\text{∗}}$$$

Please find the value of the following sum.

$$$$$$\sum_{1 \le l \le r \le n}f([a_l,a_{l+1},\ldots,a_r])$$$$$$

$$$^{\text{∗}}$$$Here, $$$\oplus$$$ denotes the bitwise XOR operation.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 4\cdot 10^5$$$).

The second line of each test case contains integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \lt 2^{25}$$$).

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

Output

For each test case, output the answer to the problem on a separate line.

Example
Input
4
5
5 4 6 7 5
5
3 3 2 2 3
1
67
10
1827481 5921082 14619611 643973 6718274 2948 244716 29 0 6717827
Output
43
21
67
36695941
Note

In the first test case, for example, consider $$$f([5,4,6,7,5])$$$

By incrementing $$$b_2=4$$$ by $$$1$$$, $$$b$$$ becomes $$$[5,5,6,7,5]$$$, and $$$5 \oplus 5 \oplus 6 \oplus 7 \oplus 5 = 4$$$.

It can be shown that $$$b_1 \oplus b_2 \oplus b_3 \oplus b_4 \oplus b_5$$$ cannot be smaller than $$$4$$$ after one dot increment.

The sum of minimum values over all subarrays can be shown to be $$$43$$$.