← 返回题目列表

Codeforces · 2238/B

B. 深红三元组

中文机器翻译题面 查看原题

脊背发凉……
— 泰拉瑞亚

召唤下一个 Boss - 克苏鲁之脑后,你注意到它周围有 $$$n$$$ 眼睛,编号从 $$$1$$$ 到 $$$n$$$。在一次攻击中,克苏鲁之脑选择了三只眼睛(不一定不同),编号为 $$$(a, b, c)$$$。三眼称为 深红色 当且仅当以下属性成立:

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

为了打败boss,你想知道克苏鲁之脑有多少种选择深红三眼的方法。如果 $$$a_1 \neq a_2$$$ 或 $$$b_1 \neq b_2$$$ 或 $$$c_1 \neq c_2$$$ 则认为眼睛三元组 $$$(a_1, b_1, c_1)$$$ 和 $$$(a_2, b_2, c_2)$$$ 不同。

$$$^{\text{*}}$$$$$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。

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

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

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

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

输出

对于每个测试用例,输出一个整数——选择深红色三只眼睛的方法数。

示例

输入
复制

3
1
2
20

输出
复制

1
5
612

注意

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

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