N. Solvable Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a zero-indexed array $$$a$$$ of size $$$2^k$$$. For each $$$x$$$ from $$$0$$$ through $$$2^k-1$$$, consider the array $$$b_x$$$ where $$$(b_x)_i = a_{i \oplus x}$$$, where $$$\oplus$$$ denotes the bitwise XOR operator. Note that because $$$a$$$ is of size $$$2^k$$$ and is zero-indexed, this array is well-defined.

Given an array $$$c$$$ of size $$$n$$$, let $$$\texttt{inv}(c)$$$ denote the number of inversions in $$$c$$$, in other words, the number of pairs $$$(i, j)$$$ where $$$0 \le i \lt j \lt n$$$ and $$$c_i \gt c_j$$$.

Your task is to compute $$$\sum_{x=0}^{2^k-1} \texttt{inv}(b_x)$$$.

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 $$$k$$$ ($$$1 \le k \le 18$$$), indicating that the length of the array $$$a$$$ is $$$2^k$$$.

The second line of each test case contains $$$2^k$$$ integers $$$a_0, a_1, \cdots a_{2^k-1}$$$ ($$$1 \le a_i \le 2^k$$$) — the contents of the array $$$a$$$.

It is guaranteed that the sum of $$$2^k$$$ over all test cases does not exceed $$$2^{18}$$$.

Output

For each test case, print a single integer — the total number of inversions across all $$$b_x$$$.

Example
Input
3
2
4 4 1 4
1
2 2
3
8 2 5 1 6 2 3 2
Output
6
0
100
Note

In the first test case, we have

  • $$$b_0 = [4, 4, 1, 4]$$$ with $$$2$$$ inversions $$$(0, 2)$$$ and $$$(1, 2)$$$
  • $$$b_1 = [4, 4, 4, 1]$$$ with $$$3$$$ inversions $$$(0, 3)$$$, $$$(1, 3)$$$, and $$$(2, 3)$$$
  • $$$b_2 = [1, 4, 4, 4]$$$ with no inversions
  • $$$b_3 = [4, 1, 4, 4]$$$ with one inversion $$$(0, 1)$$$

So the total number of inversions is $$$6$$$.

In the second test case, all elements of $$$a$$$ are equal, so none of the $$$b_i$$$ will have any inversions.