CF2238B Crimson Triples

你感到一阵寒意袭来…… —— Terraria 在召唤下一个Boss——Cthulhu之脑后，你发现它周身环绕着 $n$ 只眼睛，编号为 $1$ 到 $n$。在一次攻击中，Cthulhu之脑会选择一组三元组 $(a, b, c)$（三者不一定不同）的眼睛编号。称这组三元组为“crimson”，当且仅当它满足如下条件： $\gcd(\operatorname{lcm}(a, b), \operatorname{lcm}(b, c)) = \gcd(a, c)$。 为了打败Boss，你想知道 Cthulhu之脑 一共可以用多少种不同方式选择符合条件的“crimson”三元组。三元组 $(a_1, b_1, c_1)$ 和 $(a_2, b_2, c_2)$ 当且仅当 $a_1 \neq a_2$、或 $b_1 \neq b_2$、或 $c_1 \neq c_2$ 时被视为不同。 $\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。 $\operatorname{lcm}(x, y)$ 表示整数 $x$ 和 $y$ 的最小公倍数。

输入包含多组测试数据。第一行包含测试用例个数 $t$（$1\leq t\leq 1000$）。 接下来每组测试数据一行，包含一个整数 $n$（$1\leq n \leq 2\times 10^5$），表示 Cthulhu之脑 的眼睛数量。 保证所有测试数据中 $n$ 的总和不超过 $2\times 10^5$。

对于每个测试用例，输出一个整数，表示选择出符合条件的“crimson”三元组的数量。

在第一个测试用例中，只有一种符合条件的三元组，即 $(1, 1, 1)$。 在第二个测试用例中，有 $5$ 种符合条件的三元组，分别为 $(1, 1, 1)$，$(1, 1, 2)$，$(2, 1, 1)$，$(2, 1, 2)$，$(2, 2, 2)$。 由 ChatGPT 5 翻译