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.

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$.