CF2065G Skibidus and Capping

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$ 的 [最小公倍数](https://zh.wikipedia.org/wiki/%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B8)。

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

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