CF2238B.Crimson Triples

Chills run down your spine...

— Terraria

After summoning the next boss — The Brain of Cthulhu, you noticed that it surrounds itself with $n$ eyes, numbered from $1$ to $n$. In one attack, The Brain of Cthulhu chooses a triple of eyes (not necessarily distinct) with numbers $(a, b, c)$. The triple of eyes is called crimson if and only if the following property holds:

$\gcd$$^{\text{∗}}$$(\operatorname{lcm}$$^{\text{†}}$$(a, b), \operatorname{lcm}(b, c)) = \gcd(a, c)$,

To defeat the boss, you want to know how many ways The Brain of Cthulhu can choose a crimson triple of eyes. The triples of eyes $(a_1, b_1, c_1)$ and $(a_2, b_2, c_2)$ are considered different if $a_1 \neq a_2$, or $b_1 \neq b_2$, or $c_1 \neq c_2$.

$^{\text{∗}}$$\gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$.

$^{\text{†}}$$\operatorname{lcm}(x, y)$ denotes the lowest common divisor (LCM) of integers $x$ and $y$.

寒意顺着你的脊背流下……

——《泰拉瑞亚》

在召唤下一个 Boss —— 克苏鲁之脑后，你注意到它周围环绕着 $n$ 只眼睛，编号从 $1$ 到 $n$。在一次攻击中，克苏鲁之脑会选出一个三元组（眼睛编号）$(a, b, c)$（$a,b,c$ 不必互不相同）。当且仅当满足以下条件时，该眼睛三元组被称为“猩红三元组”：

$$\gcd^{\text{∗}}(\operatorname{lcm}^{\text{†}}(a, b), \operatorname{lcm}(b, c)) = \gcd(a, c),$$

为击败 Boss，你需要计算克苏鲁之脑能选出多少种不同的猩红三元组。若 $(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$，则视为不同三元组。

$^{\text{∗}}$ $\gcd(x, y)$ 表示整数 $x$ 与 $y$ 的最大公约数（GCD）。

$^{\text{†}}$ $\operatorname{lcm}(x, y)$ 表示整数 $x$ 与 $y$ 的最小公倍数（LCM）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

The only line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of eyes of The Brain of Cthulhu.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。随后是各测试用例的描述。

每个测试用例仅一行，包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——即克苏鲁之脑的眼睛数量。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, output one integer — the number of ways to choose a crimson triple of eyes.

对于每个测试用例，输出一个整数——选择一组绯红眼三元组的方法数。

In the first test case, there is $1$ possible crimson triple: $(1, 1, 1)$.

In the second test case, there are $5$ possible crimson triples: $(1, 1, 1)$, $(1, 1, 2)$, $(2, 1, 1)$, $(2, 1, 2)$, $(2, 2, 2)$.

在第一个测试用例中，存在 $1$ 个可能的深红色三元组：$(1, 1, 1)$。

在第二个测试用例中，存在 $5$ 个可能的深红色三元组：$(1, 1, 1)$、$(1, 1, 2)$、$(2, 1, 1)$、$(2, 1, 2)$、$(2, 2, 2)$。