P10853 [MX-X2-T2] "Cfz Round 4" Xor Counting

生きてもいいような　気がして Or maybe it is fine to just keep living like this. 繰返し笑い合うんだ　居たくなる旅 I want a journey full of repeated laughter, one that makes me want to stay.

Given a sequence $a_1, \ldots, a_n$ of length $n$ consisting of **non-negative integers**. Please find the number of index pairs $(i, j)$ that satisfy $a_i \le (a_i \oplus a_j) \le a_j$. Here, $\oplus$ denotes **bitwise XOR**, i.e. `^` in C++.

**This problem contains multiple test cases.** The first line contains an integer $T$, denoting the number of test cases. Then each test case is given as follows: - The first line contains an integer $n$. - The second line contains $n$ integers $a_1, \ldots, a_n$.

For each test case, output one integer per line, denoting the number of index pairs $(i, j)$ that satisfy the condition.

**[Sample Explanation]** For the $1$-st test case, the index pairs that satisfy the condition are $(2,1),(2,2),(2,3),(2,4),(3,1),(3,4)$. **[Constraints]** Let $\sum n$ denote the sum of $n$ within a single test point. For all testdata, $1 \le T \le 1000$, $1 \le n \le 5\times10^5$, $0 \le a_i \lt 2^{30}$, $\sum n \le 5\times10^5$. **This problem uses bundled judging.** - Subtask 1 (30 points): $\sum n \le 1000$. - Subtask 2 (30 points): $a_i \ge 1$. - Subtask 3 (40 points): no special constraints. Translated by ChatGPT 5