题目描述

小海棠有一个数组，她对每次会从中挑选出两个数字做异或和，她想知道对这个数组的所有数字进行完所有可能采样后的异或和的和是多少，即 求得以下公式的值 $\sum^{i=n,j=n}_{i=1,j=i+1} a_i\bigoplus a_j$ 其中$\bigoplus$表示按位异或。

输入描述

多组测试样例，第一行包含一个整数T表示样例组。 每组样例中，第一行包含一个整数n表示数组长度，第二行包含n个用空格分离的数字

输出描述

对于每个样例，输出一个数字表示异或和的和。

样例

输入1

2
2
1 2
3
1 2 3

输出1

3
6

提示

异或操作，英文为exclusive OR，缩写成xor。在二进制表示中，如果两个数的对应位置两个值不相同，则异或结果为1。 如果两个值相同，异或结果为0。 例如6和2的二进制分别问110和010，则异或为100。 在python和C/C++中，如果有两个变量a,b，则它们的异或可以用a^b表示。

$T<=10, n<=1000000$ 数组中的数字不超过$10^9$