题目描述

给定一个正整数 $n$。

请计算有多少个三元组 $(a,b,c)$ 满足以下条件：

• $1 \le a, b, c \le n$；
• $\gcd(\text{lcm}(a,b), \text{lcm}(b,c)) = \gcd(a,c)$。

$\gcd(x, y)$ 表示正整数 $x$ 和 $y$ 的最大公约数，

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

如果两个三元组 $(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$），则认为它们是不同的。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

对于每个测试用例，仅包含一行一个整数 $n$（$1 \le n \le 2 \times 10^5$）。

输出格式

对于每个测试用例，输出一行一个整数，表示满足条件的三元组 $(a,b,c)$ 的数量。

样例输入 1

3
1
2
20

样例输出 1

1
5
612

说明

样例解释

• 在第一个测试用例中，有 $1$ 个满足条件的三元组：$(1,1,1)$。
• 在第二个测试用例中，有 $5$ 个满足条件的三元组：$(1,1,1)$、$(1,1,2)$、$(2,1,1)$、$(2,1,2)$ 和 $(2,2,2)$。

数据范围

• 对于所有测试点，保证 $1 \le t \le 1000$。
• 对于所有测试点，保证 $1 \le n \le 2 \times 10^5$。
• 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。