题目描述

给定长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$。

请在所有 $1\le k\le n$ 中，求

$$(a_k\oplus a_1)+(a_k\oplus a_2)+\cdots+(a_k\oplus a_n)$$

的最大值。其中 $\oplus$ 表示按位异或。

输入格式

第一行包含整数 $t$，表示测试组数。

每组测试数据第一行包含整数 $n$，第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对于每组测试数据，输出上述最大值。

样例

5
3
18 18 18
5
1 2 4 8 16
5
8 13 4 5 15
6
625 676 729 784 841 900
1
1

0
79
37
1555
0

数据范围

• $1 \le t \le 10^4$
• $1 \le n \le 2\cdot 10^5$
• $0 \le a_i < 2^{30}$
• 所有测试组的 $n$ 之和不超过 $2\cdot 10^5$

来源

Codeforces Round 1017 (Div. 4), Problem E - Boneca Ambalabu