H. 最大权独立集问题
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

给定 $$$n$$$ 个点，每个点有一个整数权值 $$$W_i$$$。

定义两点 $$$i$$$ 和 $$$j$$$ 之间存在一条无向边，当且仅当 $$$W_i \oplus W_j$$$（其中 $$$\oplus$$$ 表示按位异或运算）的二进制表示中，$$$1$$$ 的个数为奇数。

请你求出这个图的最大权独立集。即，选择一个点集满足集合内任意两点之间没有边，且集合内点的权值之和最大。定义空集的权值为 $$$0$$$。你只需要求出这个最大的权值之和。

Input

本题有多组数据。

输入一行一个正整数 $$$t$$$（$$$1 \le t \le 10^5$$$），表示测试数据组数。

每组数据中：

第一行一个正整数 $$$n$$$（$$$1 \le n \le 5 \times 10^5$$$），表示点数。

第二行 $$$n$$$ 个正整数 $$$W_1,W_2,\cdots,W_n$$$（$$$1 \le W_i \le 10^9$$$），表示点的权值。

保证 $$$1 \le \sum n \le 5 \times 10^5$$$。

Output

每组数据输出一行一个整数，表示最大权独立集的权值之和。

Example
Input
3
5
3 5 15 1 2
3
6 7 11
4
1 2 4 8
Output
23
18
15