Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×
I. Valid Pairs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sherbiny and Elgoker just raided a marine base and stole a lockbox. To open it, they have to decipher treasure codes from an array $$$a$$$ of $$$n$$$ positive numbers.

Elgoker figures out the puzzle: a pair of places $$$(i, j)$$$ is a match if $$$1 \le i \lt j \le n$$$ and $$$a_{i} \oplus a_{j} \le \min(a_{i}, a_{j})$$$, where $$$\oplus$$$ is the bitwise XOR operation.

Help Sherbiny find the number of matches so they can pop the lock and get the loot!

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 2 \times 10^{5}$$$) — the length of the array.

The second line contains $$$n$$$ integers $$$a_{1}, a_{2}, \dots, a_{n}$$$ ($$$1 \le a_{i} \lt 2^{30}$$$).

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

Output

For each test case, output one integer — the number of matches.

Example
Input
4
5
1 2 3 4 7
6
8 9 10 15 16 31
2
1 1073741823
4
5 5 5 5
Output
2
7
0
6
Note

In the first test case, the valid pairs of indices are (2,3) and (4,5). Their XOR values are $$$2\oplus3=1$$$ and $$$4\oplus7=3$$$, respectively.

In the third test case, the only pair is not valid.

In the fourth test case, every pair is valid, so the answer is $$$\frac{4\times3}{2}=6$$$.