解题思路

我们可以多次选择当前数组中的某个数 x，把所有元素同时变为 a_i xor x。关键观察：

• 设经过若干次操作后，整体等价于把所有元素都异或了某个值 g。
• 若第一步选的是 x=a_k，则 g=a_k；第二步必须从新数组中选 x'=a_j xor a_k，于是新的整体异或量变为 g'=a_k xor (a_j xor a_k)=a_j；继续下去可证明每一步后的整体异或量始终是原数组中的某个元素。
• 因此，最终可达的数组恰为：{a_i xor g}，其中 g ∈ {0} ∪ {a_1,…,a_n}（允许不操作时 g=0）。

于是问题化简为：在有限候选集合 G={0} ∪ {a_i} 中，选择 g 最大化

题目内容

给定一个由 $n$ 个非负整数构成的数组 {$a_1,a_2,…,a_n$} 。你可以进行以下操作任意次(可以不执行任何操作)：

• 选择一个当前在数组中的数 $x$ ，对数组中所有元素执行按位异或运算，即将 $a_i$ 变为 $a_i$ $xor$ $x$ 。

你的目标是使操作后数组中所有元素之和最大化，输出该最大值。

【名词解释】

$xor$ ：指位运算中的按位异或运算。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≤ T≤2×10^5)$ 代表数据组数，每组测试数据描述如下：

第一行输入一个整数 $n(1≦n≦2×10^5)$ 表示数组中元素的个数。

第二行输入 $n$ 个整数 $a_1,a_2,…,a_n(0 ≦ a_i≦ 10^9)$ ，表示数组中的元素。

除此之外，保证单个测试文件的几之和不超过 $2 × 10^5$ 。

输出描述

对于每组测试数据，新起一行，输出一个整数，表示经过若干次操作后数组元素之和的最大值。

样例1

输入

3
3
2 3 4
6
1 1 4 5 1 4
7
1 9 1 9 8 1 0

输出

13
16
37

说明

对于第一组测试数据，最优方案为选择 $x = a_3 = 4$ ，操作后数组变为 {$6,7,0$}，数组元素之和为 $13$ 。可以证明，这是可以达到的最大值。