F1. Partition and Alternating Sum(easy version)
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is the easy version of the problem.The only difference is the time limit and memory limit.

You are given an array $$$a$$$ of size $$$n$$$.

You do the following operation:

  1. First you choose an integer $$$k(1 \leq k \leq n)$$$
  2. Then choose $$$k$$$ intervals $$$[l_i,r_i](1 \leq i \leq k,l_1=1,r_k=n)$$$ and $$$(l_{j+1}=r_j+1$$$ for $$$1 \leq j \leq k-1)$$$.

Note $$$s_i=a_{l_i}|a_{l_{i+1}}$$$ $$$|...|a_{r_i}$$$.Here $$$|$$$ means bitwise-or.

Find the maximum of $$$Σ_{i=1}^k(-1)^{i+1}*s_i$$$.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^6)$$$, denoting the number of test cases.

Each test case consists of multiple lines of input.

The first line of each test case contains an integer $$$n(1 \leq n \leq 10^6)$$$.

The next lines contains $$$n$$$ space-separated integers:$$$a_1$$$,$$$a_2$$$,...$$$a_n$$$ $$$(0 \leq a_i \lt 2^{30})$$$.

The sum of $$$n$$$ over all test cases won't exceed $$$10^6$$$.

Output

For each test case, output on a new line — the maximum of $$$Σ_{i=1}^k(-1)^{i+1}*s_i$$$.

Example
Input
4
3
2 1 2
6
6 6 6 6 6 6
7
7 0 5 4 4 2 6
6
9 4 6 8 1 7
Output
3
6
16
25
Note

Test case $$$1$$$:

Choose $$$k=3,[l_1,r_1]=[1,1],[l_2,r_2]=[2,2],[l_3,r_3]=[3,3]$$$.

We get $$$s_1=2,s_2=1,s_3=2$$$.The answer is $$$s_1-s_2+s_3=2-1+2=3$$$.

Test case $$$2$$$:

Choose $$$k=1,[l_1,r_1]=[1,6]$$$.

We get $$$s_1=6$$$.The answer is $$$s_1=6$$$.