← 返回题目列表

Codeforces · 1899/D

D. Yarik 和音符

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

Yarik 是多种音乐的忠实粉丝。但 Yarik 不仅喜欢听音乐,还喜欢写音乐。他最喜欢电子音乐,所以他创建了自己的音符系统,在他看来,这是最适合的。

由于 Yarik 也喜欢信息学,因此在他的系统中注释用整数 $$$2^k$$$ 表示,其中 $$$k \ge 1$$$ — 一个正整数。但是,如您所知,您不能仅使用音符来创作音乐,因此 Yarik 使用两个音符的组合。两个音符 $$$(a, b)$$$ 的组合,其中 $$$a = 2^k$$$ 和 $$$b = 2^l$$$,他用整数 $$$a^b$$$ 表示。

例如,如果 $$$a = 8 = 2^3$$$、$$$b = 4 = 2^2$$$,则组合 $$$(a, b)$$$ 由整数 $$$a^b = 8^4 = 4096$$$ 表示。请注意,不同的组合可以具有相同的表示法,例如,组合 $$$(64, 2)$$$ 也由整数 $$$4096 = 64^2$$$ 表示。

Yarik 已经选择了他想要在新旋律中使用的 $$$n$$$ 音符。然而,由于它们的整数可能非常大,他将它们写成一个长度为$$$n$$$的数组$$$a$$$,那么注释$$$i$$$就是$$$b_i = 2^{a_i}$$$。数组 $$$a$$$ 中的整数可以重复。

旋律将由两个音符的多种组合组成。 Yarik 想知道有多少对音符 $$$b_i, b_j$$$ $$$(i < j)$$$ 使得组合 $$$(b_i, b_j)$$$ 等于组合 $$$(b_j, b_i)$$$。换句话说,他想要计算 $$$(i, j)$$$ $$$(i < j)$$$ 的数量,使得 $$$b_i^{b_j} = b_j^{b_i}$$$。帮助他找出这样的对的数量。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

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

下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组 $$$a$$$。

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

输出

对于每个测试用例,输出满足给定条件的对的数量。

示例

输入 #1

5
1
2
4
3 1 3 2
2
1000 1000
3
1 1 1
19
2 4 1 6 2 8 5 4 2 10 5 10 8 7 4 3 2 6 10

输出 #1

0
2
1
3
19