优化很有趣！尤其是当它并非严格必要的时候。

众所周知，位运算（例如按位异或）比递归函数（例如最大公约数，GCD）要快。为了给你的实习主管留下深刻印象，你在公司的旗舰项目中将所有 $gcd(x, y)$ 的实例都替换成了速度更快的 $xor(x, y)$。

那是昨天，星期五的事了。现在你开始思考在部署到生产环境之前是否应该测试一下你的新代码……好吧，亡羊补牢，为时未晚。给定一个数字序列 $a_1, \dots, a_n$，确定有多少对 $(i, j)$ ($1 \le i < j \le n$) 实际上满足 $gcd(a_i, a_j) = xor(a_i, a_j)$。回想一下，$gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公约数，而 $xor(x, y)$ 是 $x$ 和 $y$ 的按位异或运算。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 20$)。接下来是各测试用例的描述。 每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2\,000\,000$)。第二行包含整数 $a_1, a_2, \dots, a_n$，所有整数均为正数且不超过 $1\,000\,000$。 所有测试用例中序列的总长度不超过 $3 \cdot 10^7$。

输出格式

对于每个测试用例，输出一个整数：满足 $gcd(a_i, a_j) = xor(a_i, a_j)$ 的下标对 $(i, j)$ ($i < j$) 的数量。

样例

样例输入 1

1
4
2 3 4 3

样例输出 1

2