Given a sequence of $n$ non-negative integers $a_1, \ldots, a_n$.

Find the number of index pairs $(i, j)$ such that $a_i \le (a_i \oplus a_j) \le a_j$. Here, $\oplus$ denotes the bitwise XOR operation, which corresponds to ^ in C++.

Input

The first line contains an integer $T$, representing the number of test cases.

Each test case is described as follows: - The first line contains an integer $n$. - The second line contains $n$ integers $a_1, \ldots, a_n$.

Output

For each test case, output a single integer representing the number of index pairs $(i, j)$ that satisfy the condition.

Examples

Input 1

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

Output 1

6
6
0
1
3
12
65

Note 1

For the first 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$ over all test cases in a single test file.

For all test cases, $1 \le T \le 1000$, $1 \le n \le 5\times10^5$, $0 \le a_i < 2^{30}$, and $\sum n \le 5\times10^5$.

This problem uses bundled testing.

• Subtask 1 (30 points): $\sum n \le 1000$.
• Subtask 2 (30 points): $a_i \ge 1$.
• Subtask 3 (40 points): No additional constraints.