← 返回题目列表

Codeforces · 2065/G

G. 斯基比度斯和封盖

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

斯基比杜斯被阿莫格的外星人绑架了!斯基比杜斯试图说服自己摆脱困境,但阿莫格外星人不相信他。为了证明他没有完全上限,阿莫格外星人要求他解决这个任务:

如果整数 $$$x$$$ 可以写为 $$$p \cdot q$$$,其中 $$$p$$$ 和 $$$q$$$ 是(不一定不同)素数,则该整数被视为半素数。例如,$$$9$$$ 是半素数,因为它可以写为 $$$3 \cdot 3$$$,而 $$$3$$$ 是素数。

Skibidus 被给予一个包含 $$$n$$$ 整数的数组 $$$a$$$。他必须报告 $$$(i, j)$$$ 对的数量,使得 $$$i \leq j$$$ 和 $$$\operatorname{lcm}(a_i, a_j)$$$$$$^{\text{*}}$$$ 是半素数。

输入

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

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

以下行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$2 \leq a_i \leq n$$$)。

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

输出

对于每个测试用例,在新行上输出有序索引对的数量。

示例

输入 #1

3
4
2 2 3 4
6
2 2 3 4 5 6
9
2 2 4 5 7 8 9 3 5

输出 #1

5
12
18

注意

在第一个测试用例中,$$$5$$$ 索引对是 $$$(1, 3)$$$、$$$(1, 4)$$$、$$$(2, 3)$$$、$$$(2, 4)$$$ 和 $$$(4, 4)$$$。