J. XOR MSB
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an array $$$a_1, a_2, \dots, a_n$$$ of length $$$n$$$. The elements $$$a_i$$$ are distinct positive integers.

Your task is to compute the following sum: $$$$$$ S = \sum_{i=1}^n \sum_{j=i+1}^n \text{MSB}(a_i \oplus a_j) $$$$$$

The operator $$$\oplus$$$ denotes the bitwise-XOR operation.

The function $$$\textbf{MSB}(x)$$$ for a positive integer $$$x$$$ denotes the index (power) of the most significant bit in the binary representation of $$$x$$$.

This is equivalent to finding the largest integer $$$k$$$ such that $$$2^k \le x$$$. The value returned is $$$k$$$.

The binary representation of $$$20$$$ is $$$10100_2$$$. The most significant bit is $$$2^4$$$. Thus, $$$\text{MSB}(20) = 4$$$, $$$\text{MSB}(13) = 3$$$, and $$$\text{MSB}(8) = 3$$$.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$), the number of test cases.

Then $$$T$$$ test cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$), the size of the array $$$a$$$.

The second line of each test case contains $$$n$$$ distinct positive integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer representing the calculated sum $$$S$$$.

Example
Input
2
5
15 3 6 8 10
4
1 2 3 4
Output
25
8