CF1884D Counting Rhyme

给定一个整数数组 $a_1, a_2, \ldots, a_n$。 如果一对整数 $(i, j)$ 满足 $1 \le i < j \le n$，并且不存在一个整数 $k$（$1 \le k \le n$），使得 $a_i$ 能被 $a_k$ 整除且 $a_j$ 也能被 $a_k$ 整除，则称这对 $(i, j)$ 是“好对”。 请你计算“好对”的数量。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$），表示测试数据组数。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 10^6$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）。 保证所有测试数据中 $n$ 的总和不超过 $10^6$。

对于每组测试数据，输出“好对”的数量。

在第一个测试用例中，没有“好对”。 在第二个测试用例中，所有的“好对”为：$(1, 2)$、$(2, 3)$ 和 $(2, 4)$。 由 ChatGPT 4.1 翻译