题目描述

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

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

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

输入格式

本题有多组数据。

输入一行一个正整数 $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$。

输出格式

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

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

23
18
15