← 返回题目列表

Codeforces · 1822/G2

G2. 魔法三元组(困难版)

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

这是问题的困难版本。唯一的区别是,在此版本中,$$$a_i \le 10^9$$$。

对于给定的 $$$n$$$ 整数 $$$a$$$ 序列,如果满足以下条件,则三元组 $$$(i, j, k)$$$ 被称为 magic:

- $$$1 \le i, j, k \le n$$$。
- $$$i$$$、$$$j$$$、$$$k$$$ 成对不同。
- 存在一个正整数 $$$b$$$ 使得 $$$a_i \cdot b = a_j$$$ 和 $$$a_j \cdot b = a_k$$$。

Kolya 收到了一系列整数 $$$a$$$ 作为礼物,现在想要计算它的魔法三元组的数量。帮助他完成这个任务!

请注意,整数 $$$i$$$、$$$j$$$ 和 $$$k$$$ 的顺序没有限制。

输入

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

测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — 序列的长度。

测试的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 序列 $$$a$$$ 的元素。

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

输出

对于每个测试用例,输出一个整数 - 序列 $$$a$$$ 的幻三元组数。

示例

输入 #1

7
5
1 7 7 2 7
3
6 2 18
9
1 2 3 4 5 6 7 8 9
4
1000 993 986 179
7
1 10 100 1000 10000 100000 1000000
8
1 1 2 2 4 4 8 8
9
1 1 1 2 2 2 4 4 4

输出 #1

6
1
3
0
9
16
45

注意

在第一个示例中,序列 $$$a$$$ 有 $$$6$$$ 魔术三元组 — $$$(2, 3, 5)$$$, $$$(2, 5, 3)$$$, $$$(3, 2, 5)$$$, $$$(3, 5, 2)$$$, $$$(5, 2, 3)$$$,$$$(5,3,2)$$$。

在第二个示例中,序列 $$$a$$$ — $$$(2, 1, 3)$$$ 有一个神奇的三元组。