← 返回题目列表

Codeforces · 1420/B

B. 岩石和杠杆

中文机器翻译题面 查看原题

Danik 迫切需要摇滚和杠杆!显然,获得这些东西最简单的方法就是向隐士蜥蜴要。

隐士蜥蜴同意给丹尼克杠杆。但要获得石头,丹尼克需要解决以下任务。

给定一个正整数 $$$n$$$ 和一个正整数数组 $$$a$$$。任务是计算 $$$(i,j)$$$ 满足 $$$i<j$$$ 和 $$$a_i$$$ $$$\&$$$ $$$a_j \ge a_i \oplus a_j$$$ 的数量,其中 $$$\&$$$ 表示按位 AND 运算,$$$\oplus$$$ 表示按位 XOR 运算。

Danik 已经解决了这个任务。但你能解决吗?

输入

每个测试包含多个测试用例。

第一行包含一个正整数 $$$t$$$ ($$$1 \le t \le 10$$$) 表示测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个正整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组的长度。

第二行包含 $$$n$$$ 正整数 $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — 数组的元素。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,打印一个非负整数 - 问题的答案。

示例

输入 #1

5
5
1 4 3 7 10
3
1 1 1
4
6 2 5 3
2
2 4
1
1

输出 #1

1
3
2
0
0

注意

在第一个测试用例中只有一对:$$$(4,7)$$$:$$$4$$$ $$$\&$$$ $$$7 = 4$$$,$$$4 \oplus 7 = 3$$$。

在第二个测试用例中,所有对都很好。

在第三个测试用例中,有两对:$$$(6,5)$$$ 和 $$$(2,3)$$$。

在第四个测试用例中没有好的对。