P16340 「ALFR Round 10」XOR and Simple Trick

Given a sequence $a$ of $n$ non-negative integers, find the number of pairs of indices $(i, j)$ such that $1 \le i < j \le n$, and for every $a_k$ and every non-negative integer $x$, the following condition holds: $a_k \oplus x \le a_i \oplus x$ OR $a_k \oplus x \ge a_j \oplus x$.

This problem contains multiple test cases. The first line contains a positive integer $T$, representing the number of test cases. For each test case: - The first line contains a positive integer $n$. - The second line contains $n$ non-negative integers, where the $i$-th number represents $a_i$.

For each test case, output a single integer representing the answer.

**【Explanation of Sample 1】** For the first test case, the valid pairs $(i, j)$ are $(1, 4)$ and $(2, 3)$. **【Constraints】** Let $\sum n$ be the sum of $n$ over all test cases in a single test file, and $V$ be the maximum value of $a_i$ in a single test file. For all test cases: - $1 \le T \le 5 \times 10^5$ - $2 \le n, \sum n \le 10^6$ - $0 \le a_i < 2^{30}$ for all $1 \le i \le n$ - All $a_i$ are distinct within a single test case. **This problem uses bundled testing.** Subtasks are as follows: | Subtask | $\sum n \le$ | $V