Background

生きてもいいような　気がして
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.

Problem Description

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++.

Input Format

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$.

Output Format

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

7
4
3 0 1 3
5
0 1 2 3 4
1
6
1
0
6
1 1 4 5 1 4
10
10 32 43 28 19 83 10 10 83 23
15
132 256 852 31 1 0 12 13 12 0 0 255 143 23 32

6
6
0
1
3
12
65

Hint

[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