斯基比杜斯被阿莫格的外星人绑架了!斯基比杜斯试图说服自己摆脱困境,但阿莫格外星人不相信他。为了证明他没有完全上限,阿莫格外星人要求他解决这个任务:
如果整数 $$$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)$$$。