E. [Yellow] Can you do the OR math ?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After his students easily solved his previous assignment involving Abushogi's bizarre function, MrMoon felt deeply humiliated.

Determined to take his revenge and finally stump his students, MrMoon has created a new version, he decided that instead of replacing the elements with "$$$x$$$ AND $$$y$$$", the game will now replace them with "$$$x$$$ OR $$$y$$$".

MrMoon is now struggling to calculate the answers himself and needs your help to verify his test cases. You are given an array $$$a$$$ of size $$$n$$$. You play a game exactly $$$n-1$$$ operations. In each operation, you do the following:

  • Choose any two elements $$$x$$$ and $$$y$$$ from the array and remove them;
  • Add $$$\max(x, y)$$$ to your score;
  • Insert a single element equal to $$$x \ \vert{} \ y$$$ (the bitwise OR of $$$x$$$ and $$$y$$$) back into the array.

The game ends after exactly $$$n-1$$$ operations when only one element remains. (If $$$n=1$$$, you make $$$0$$$ operations and your score is $$$0$$$).

Let $$$f(a)$$$ be the maximum possible score you can achieve from the array $$$a$$$. Your task is to find $$$f(a)$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — denotes the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — denotes the size of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^7$$$) — denotes the elements of the array.

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

Output

For each test case, output a single integer — the maximum possible score $$$f(a)$$$ you can achieve after $$$n-1$$$ operations.

Example
Input
3
3
3 2 4
1
10
4
1 2 4 8
Output
11
0
34
Note

In the first test case, the array is [3, 2, 4]. The optimal strategy is as follows: Choose $$$x = 4$$$ and $$$y = 3$$$. You add $$$\max(4, 3) = 4$$$ to your score. You remove $$$4$$$ and $$$3$$$, and insert $$$4 \ \vert{} \ 3 = 7$$$ back into the array. The array becomes [7, 2]. Choose $$$x = 7$$$ and $$$y = 2$$$. You add $$$\max(7, 2) = 7$$$ to your score. You remove $$$7$$$ and $$$2$$$, and insert $$$7 \ \vert{} \ 2 = 7$$$ back into the array. The array becomes [7].

The game ends because only one element remains. Your total score is $$$4 + 7 = 11$$$.

In the second test case, $$$n = 1$$$, so you perform $$$0$$$ operations and the total score is $$$0$$$.

In the third test case, the array is [1, 2, 4, 8]. First, pair $$$8$$$ and $$$4$$$. Score increases by $$$8$$$, insert $$$8 \ \vert{} \ 4 = 12$$$. Array is [1, 2, 12].Next, pair $$$12$$$ and $$$2$$$. Score increases by $$$12$$$, insert $$$12 \ \vert{} \ 2 = 14$$$. Array is [1, 14].Finally, pair $$$14$$$ and $$$1$$$. Score increases by $$$14$$$, insert $$$14 \ \vert{} \ 1 = 15$$$. Array is [15].Total score = $$$8 + 12 + 14 = 34$$$.