Chef has a binary array A of length N. In one operation, Chef does the following:

1. Select any L and R such that (1 ≤ L < R ≤ |A|) \
2. Add $A_{L} \oplus A_{L+1} \oplus \ldots \oplus A_{R}$ to his $*score* (Here, \oplus$ denotes the [bitwise XOR operation] \
3. Remove the subarray $A_{L \dots R}$ from A

Determine the maximum score Chef can get after performing the above operation any number of times.

------ Input Format ------

• The first line contains a single integer T — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N — the size of the array A.
• The second line of each test case contains $N space-separated integers A_{1}, A_{2}, \dots, A_{N}$ denoting the array A.

------ Output Format ------

For each test case, output the maximum score Chef can get.

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$A_{i} \in \{0, 1\}$
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------
3
5
1 0 0 0 1
3
1 1 1
3
0 0 0

----- Sample Output 1 ------
2
1
0

----- explanation 1 ------
Test Case 1: We can perform the following moves:
- $A = [1, 0, 0, 0, 1]$. Select $L = 1$ and $R = 3$ and remove subarray $[1, 0, 0]$. $A$ becomes $[0, 1]$.
- $A = [0, 1]$. Select $L = 1$ and $R = 2$ and remove subarray $[0, 1]$. $A$ becomes $[]$.

Total score $= 1 + 1 = 2$

Test Case 2: We can perform the following move:
- $A = [1, 1, 1]$. Select $L = 1$ and $R = 3$ and remove subarray $[1, 1, 1]$. $A$ becomes $[]$.

Total score $= 1$

见题面

见题面