F2. Partition and Alternating Sum(hard version)
time limit per test
1 second
memory limit per test
4 megabytes
input
standard input
output
standard output

This is the hard 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$$$.