题目描述

Skibidus 被 Amog 外星人绑架了！Skibidus 试图以言辞自辩脱身，但 Amog 外星人不相信他。为了证明自己不是在撒谎(capping)，Amog 外星人要求他解决以下问题：

一个整数 $x$ 如果可以写成 $p \cdot q$ 的形式（$p$ 和 $q$ 均为质数，可以相同），则称其为半质数。例如，$9$ 是半质数，因为它可以写成 $3 \cdot 3$，而 $3$ 是质数。

Skibidus 得到了一个包含 $n$ 个整数的数组 $a$。他需要统计所有满足 $i \leq j$ 且 $\operatorname{lcm}(a_i, a_j)$ $^{\text{∗}}$ 为半质数的索引对 $(i, j)$ 的数量。

$^{\text{∗}}$ 给定两个整数 $x$ 和 $y$，$\operatorname{lcm}(x, y)$ 表示 $x$ 与 $y$ 的 最小公倍数。

输入格式

第一行包含一个整数 $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$。

输出格式

对于每个测试用例，输出一行一个整数，表示满足条件的有序索引对 $(i, j)$ 的数量。

样例

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

5
12
18

样例说明

在第一个测试用例中，满足条件的 $5$ 个索引对分别为 $(1, 3)$、$(1, 4)$、$(2, 3)$、$(2, 4)$ 和 $(4, 4)$。

来源

Codeforces 2065G，英文题名 Skibidus and Capping。