该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

生きてもいいような　気がして
或者　就这样活着也不错吧

繰返し笑い合うんだ　居たくなる旅
想要有一段充满欢笑的旅程啊

题目描述

给定一个长度为 $n$ 的非负整数序列 $a_1, \ldots, a_n$。

请你求出满足 $a_i \le (a_i \oplus a_j) \le a_j$ 的下标对 $(i, j)$ 的数量。其中 $\oplus$ 表示按位异或，即 C++ 中的 ^。

输入格式

本题有多组测试数据。

输入的第一行包含一个整数 $T$，表示测试数据组数。

接下来依次输入每组测试数据。对于每组测试数据：

• 第一行一个整数 $n$。
• 第二行 $n$ 个整数 $a_1, \ldots, a_n$。

输出格式

对于每组测试数据，输出一行一个整数，表示满足条件的下标对 $(x,y)$ 的数量。

样例

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

样例解释

对于第 $1$ 组测试数据，满足条件的下标对有 $(2,1),(2,2),(2,3),(2,4),(3,1),(3,4)$。

数据范围

设 $\sum n$ 表示单个测试点中 $n$ 的和。

对于所有测试数据，$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$。

本题采用捆绑测试。

• Subtask 1（30 points）：$\sum n \le 1000$。
• Subtask 2（30 points）：$a_i \ge 1$。
• Subtask 3（40 points）：无特殊限制。