Problem Description

Given $n$ vertices, each vertex has an integer weight $W_i$.

Define that there is an undirected edge between vertices $i$ and $j$ if and only if, in the binary representation of $W_i \oplus W_j$ (where $\oplus$ denotes bitwise XOR), the number of $1$ bits is odd.

Please find the maximum weight independent set of this graph. That is, choose a set of vertices such that there is no edge between any two vertices in the set, and the sum of weights of the chosen vertices is as large as possible. The weight of the empty set is defined as $0$. You only need to output this maximum total weight.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $t$ ($1 \le t \le 10^5$), which denotes the number of test cases.

For each test case:

The first line contains a positive integer $n$ ($1 \le n \le 5 \times 10^5$), which denotes the number of vertices.

The second line contains $n$ positive integers $W_1,W_2,\cdots,W_n$ ($1 \le W_i \le 10^9$), which denote the weights of the vertices.

It is guaranteed that $1 \le \sum n \le 5 \times 10^5$.

Output Format

For each test case, output one integer per line, representing the maximum total weight of an independent set.

3
5
3 5 15 1 2
3
6 7 11
4
1 2 4 8

23
18
15

Hint

Translated by ChatGPT 5