Rock and Lever
Contest: Codeforces Round 672 (Div. 2)
Difficulty rating: 1200
Tags: bitmasks, math

Danik urgently needs rock and lever! Obviously, the easiest way to get these things is to ask Hermit Lizard for them.

Hermit Lizard agreed to give Danik the lever. But to get a stone, Danik needs to solve the following task.

You are given a positive integer $$$n$$$, and an array $$$a$$$ of positive integers. The task is to calculate the number of such pairs $$$(i,j)$$$ that $$$i<j$$$ and $$$a_i$$$ $$$\&$$$ $$$a_j \ge a_i \oplus a_j$$$, where $$$\&$$$ denotes the bitwise AND operation, and $$$\oplus$$$ denotes the bitwise XOR operation.

Danik has solved this task. But can you solve it?

Input format:
Each test contains multiple test cases.

The first line contains one positive integer $$$t$$$ ($$$1 \le t \le 10$$$) denoting the number of test cases. Description of the test cases follows.

The first line of each test case contains one positive integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — length of the array.

The second line contains $$$n$$$ positive integers $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — elements of the array.

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

Output format:
For every test case print one non-negative integer — the answer to the problem.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case there is only one pair: $$$(4,7)$$$: for it $$$4$$$ $$$\&$$$ $$$7 = 4$$$, and $$$4 \oplus 7 = 3$$$.

In the second test case all pairs are good.

In the third test case there are two pairs: $$$(6,5)$$$ and $$$(2,3)$$$.

In the fourth test case there are no good pairs.

Example input:
5
5
1 4 3 7 10
3
1 1 1
4
6 2 5 3
2
2 4
1
1

Example output:
1
3
2
0
0

Editorial:
Let's take a pair $$$(a_i, a_j)$$$ and see in which case $$$a_i\ \&\ a_j \ge a_i \oplus a_j$$$ will hold. For this we will follow the bits $$$a_i$$$ and $$$a_j$$$ from highest to lowest. If we meet two zero bits, the values of $$$a_i\ \&\ a_j$$$ and $$$a_i \oplus a_j$$$ will match in this bit, so we move on. If we meet a zero bit in $$$a_i$$$ and in $$$a_j$$$ —one bit(or vice versa), then we get $$$a_i\ \&\ a_j < a_i \oplus a_j$$$, and we can immediately say that the required condition is false. And if we meet two one bits, then the required condition is fulfilled,  e. $$$a_i\ \&\ a_j > a_i \oplus a_j$$$, and then the bits can no longer be considered.
Now let's consider the highest one bit in the number of $$$a_i$$$ (let it stand at $$$p_i$$$ position) and the highest single bit in the number of $$$a_j$$$ (let it stand at $$$p_j$$$ position). (Here, we consider that the bits are numbered in order of lowest to highest.) Then, $$$p_i = p_j$$$ must hold. If $$$p_i > p_j$$$, then there is zero in the $$$a_j$$$ position and one unit in the $$$a_i$$$ position. But then from the reasoning above we get that $$$a_i\ \&\ a_j < a_i \oplus a_j$$$. The case of $$$p_i < p_j$$$ is treated in a similar way.
It is also easy to see that if $$$p_i = p_j$$$ then we automatically get the condition $$$a_i\ \&\ a_j > a_i \oplus a_j$$$.
From here the problem is solved. For each number we find the position of the highest one bit $$$p_i$$$. Then we need to calculate the number of pairs of numbers, for which $$$p_i = p_j$$$. You may notice that the answer is $$$\sum\limits_\ell \frac{k_\ell\cdot(k_\ell-1)}2$$$, where $$$k_\ell$$$ — the number of numbers for which $$$p_i = p_j$$$.
The complexity of the solution is $$$O(n)$$$.