题目描述

光头强在森林里伐木时，发现了一张神秘的数学卷轴。卷轴上记录了一个由 $n$ 个正整数组成的序列 $a_{1},a_{2},...,a_{n}$ 。

为了换取森林里那一块长势喜人的木材，光头强必须破解卷轴上的谜题。谜题要求他计算出有多少个二元对 $(i,j)$ ，满足 $1 \leq i \leq j \leq n$ ，且同时成立以下两个关于位运算的条件。

定义两个函数：

• $f_{max}(x)$ 表示 $x$ 的二进制表示中最高位的 $1$ 所代表的值（即不大于 $x$ 的最大 $2$ 的整数次幂）。例如 $f_{max}(10)=8$ （ $10$ 的二进制为 $(1010)_{2}$ ，最高位 $1$ 在第三位，权重为 $2^{3}=8$ ）。
• $f_{min}(x)$ 表示 $x$ 的二进制表示中最低位的 $1$ 所代表的值（即 lowbit(x)）。例如 $f_{min}(10)=2$ （ $10$ 的二进制为 $(1010)_{2}$ ，最低位 $1$ 在第一位，权重为 $2^{1}=2$ ）。

要求满足的条件为：

1. $f_{max}(a_{i} \oplus a_{j})=max(f_{max}(a_{i}),f_{max}(a_{j}))$
2. $f_{min}(a_{i} \oplus a_{j})=min(f_{min}(a_{i}),f_{min}(a_{j}))$

其中 $\oplus$ 表示按位异或运算。

如果光头强不能在规定时间内算出结果，熊大和熊二就会来阻止他伐木。请你帮帮他！

输入格式

输入包含多组测试数据。

第一行包含一个正整数 $T$ ，表示测试数据组数。
接下来包含 $T$ 组测试数据，每组测试数据的格式如下：

第一行包含一个正整数 $n$ ，表示序列的长度。
第二行包含 $n$ 个正整数 $a_{1},a_{2},...,a_{n}$ ，表示序列中的元素。

输出格式

对于每组测试数据，输出一个整数，表示满足条件的二元对 $(i,j)$ 的个数。

输入输出样例 #1

输入 #1

2
5
3 5 6 10 12
3
1 2 4

输出 #1

6
3

说明/提示

第一组数据：序列为 $[3,5,6,10,12]$ 。满足条件的对为 $(1,3),(1,4),(1,5),(2,4),(2,5),(3,5)$ ，共 $6$ 对。
第二组数据：序列为 $[1,2,4]$ 。满足条件的对为 $(1,2),(1,3),(2,3)$ 共 $3$ 对。

对于 $100 \%$ 的数据， $1 \leq n \leq 2 \times 10^5，1 \leq a_{i} \leq 10^9$

• 特殊性质A：保证所有 $a_{i}$ 均为 $2$ 的整数次幂。
• 特殊性质B：保证所有 $f_{max}(a_{i})$ 均相等。
• 特殊性质C：保证所有 $f_{min}(a_{i})$ 均相等。