Problem Description

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

Input Format

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

Output Format

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

4
5
1 4 5 2 6
7
3 1 4 5 9 2 6
3
114 51 4
6
1 2 4 8 16 32

2
2
1
1

Hint

【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: