题目描述

给定一个长度为 $n$ 的数组 $a$。你可以进行如下操作若干次（也可以一次都不进行）：

• 选择 $i$、$j$、$b$：交换 $a_i$ 和 $a_j$ 的二进制表示中的第 $b$ 位。

请你求出 $\max(a) - \min(a)$ 的最大可能值。

在二进制表示中，位从右（最低位）到左（最高位）编号。假设任意二进制表示的开头都有无限多个前导零。

例如，对于 $4=100_2$ 和 $3=11_2$，交换第 $0$ 位后，得到 $101_2=5$ 和 $10_2=2$。交换第 $2$ 位后，得到 $000_2=0$ 和 $111_2=7$。

这里，$\max(a)$ 表示数组 $a$ 的最大元素，$\min(a)$ 表示数组 $a$ 的最小元素。

$x$ 的二进制表示是 $x$ 用 $2$ 进制表示的结果。例如，$9$ 和 $6$ 的二进制分别为 $1001$ 和 $110$。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 128$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 512$），表示数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i < 1024$），表示数组 $a$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $512$。

输出格式

对于每个测试用例，输出一个整数，表示 $\max(a) - \min(a)$ 的最大可能值。

说明/提示

在第一个样例中，可以证明不需要进行任何操作，$\max(a) - \min(a)$ 的最大值为 $1 - 0 = 1$。

在第二个样例中，无法通过操作改变数组，$\max(a) - \min(a)$ 的最大值为 $5 - 5 = 0$。

在第三个样例中，初始 $a = [1, 2, 3, 4, 5]$，可以进行一次操作，选择 $i = 2$，$j = 5$，$b = 1$。此时数组变为 $a = [1, 0, 3, 4, 7]$。可以证明，任何进一步的操作都无法得到更优的答案，因此答案为 $\max(a) - \min(a) = 7 - 0 = 7$。

由 ChatGPT 4.1 翻译

样例

4
3
1 0 1
4
5 5 5 5
5
1 2 3 4 5
7
20 85 100 41 76 49 36

1
0
7
125