题目描述

我有一个数列 $a_1,a_2,\cdots,a_n$，每个 $a_i$ 是小于 $2^m$ 的正整数。

显然正整数的二进制表示下至少有一个 $1$，现在，我希望您能把每个数仅保留二进制下其中的某一位 $1$，并最大化这个数列中所有数的异或和。

例如，$5$ 的二进制表示为 $101$，那么 $5$ 就只能变为 $4$（保留从左往右第一个 $1$，即变为 $100$），或者 $1$（保留另一个 $1$，即变为 $001$），$11$ 的二进制表示为 $1011$，那么它可以变为 $8$（$1000$）、$2$（$0010$）、$1$（$0001$）中的某一个。

输入格式

第一行一个正整数 $T$，表示数据组数。

对于每组数据：

第一行一个正整数 $n$。

接下来一行 $n$ 个正整数，表示 $a$ 数组。

输出格式

对于每组数据输出一行一个数，表示最大的异或和。

样例输入 #1

5
7
1 2 32 64 1024 2147483648 2147483648
4
15 15 15 15
5
13 9 38 99 44
10
656 546 64 72 512 256 768 384 450 512
50
12591291 3364543 629743 169925631 172761087 328110 1301503 178655 5898239 8900607 2195167 21010431 5529071 99775 68719477090 1074130671 6592 67133439 35 65711 34143 137439085183 327 268442559 87262719 8198 9843197 67292 135852031 8656895 44671 9645055 376319 131 403201023 360706 331111 1064823 2173855 318839 1148243967 139998 16777216 1086201855 16 33556783 2687 2 84033 105655

样例输出 #1

1123
15
110
1018
207769042943

样例说明 #1

对于第一组数据，每个数二进制下都只有一个位是 $1$，所以唯一的一个方案就是全部保持原样，答案为这七个数的异或和，即 $1123$。

对于第二组数据，可以变为 $1,2,4,8$ 或者它的任意排列。

对于第三组数据，一种最优方案是变为 $4,8,2,64,32$。

对于第四组数据，一种最优方案是变为 $16,32,64,8,512,256,512,128,2,512$。

样例输入 #2

5
7
73 4 96 49 4 57 104
7
1 72 104 20 72 104 20
7
68 118 11 1 102 8 8
7
69 32 3 32 64 72 65
7
4 4 83 121 4 4 1

样例输出 #2

121
117
121
79
97

数据规模与约定

对于 $100\%$ 的数据，$1 \le T \le 5$，$1 \le n \le 100$，$1 \le m \le 60$，对所有 $i$，有 $1 \le a_i\le 2^m - 1$。

题目来源

By matthew99