F. The Decoder's Enigma
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Apraham and Nowar are two world-renowned cryptographers who have dedicated their lives to solving the world's most complex puzzles.

One day, they received a mysterious locked briefcase containing a digital screen. On the screen, there was a long sequence of $$$n$$$ numbers where $$$n$$$ is a power of $$$2$$$, represented as an array $$$a$$$ of length $$$n$$$, with indices ranging from $$$0$$$ to $$$n-1$$$.

To unlock the briefcase and reveal the secret inside, they must find all the hidden connections within the sequence. The lock's security system evaluates pairs of indices, $$$i$$$ and $$$j$$$, using two fundamental bitwise operations. For any chosen pair, it calculates the Common Factor (using Bitwise AND, $$$i \ \& \ j$$$) and the Difference Factor (using Bitwise XOR, $$$i \oplus j$$$).

'Apraham notices a small hint engraved on the back of the briefcase: "True balance is achieved only when the paths of intersection and divergence hold the exact same value.'This means a pair of indices $$$(i, j)$$$ is considered a Valid Key Pair if and only if:$$$$$$a[i \ \& \ j] = a[i \oplus j]$$$$$$Nowar needs to find the total number of these Valid Key Pairs $$$(i, j)$$$ where $$$0 \le i, j \lt n$$$ to generate the final override code and open the briefcase.

Can you help Apraham and Nowar calculate the total number of valid pairs?

Input

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

The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2^{17}$$$) — the number of elements in the array $$$a$$$. It's guaranteed that $$$n = 2^k$$$ for some $$$1 \le k \le 17$$$.

The second line of each test case contains $$$n$$$ space-separated integers $$$a_0, a_1, \dots, a_{n-1}$$$ ($$$1 \le a_i \le 2^{17}$$$) — the values inside the array.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2^{17}$$$.

Output

For each test case, output a single integer — the total number of Valid Key Pairs $$$(i, j)$$$ such that $$$0 \le i, j \lt n$$$ and $$$a[i \ \& \ j] = a[i \oplus j]$$$.

Example
Input
4
4
1 2 3 4
8
5 5 5 5 5 5 5 5
2
1 1
16
7 3 9 2 8 1 6 4 5 9 3 7 2 8 4 6
Output
1
64
4
30