You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题陈述

最近，小A在夏令营学习了一个新课题--欧几里得算法。

当他意识到 $a \cdot b = lcm(a, b) \cdot gcd(a, b)$ ，其中 $gcd(a, b)$ 是 $a$ 和 $b$ 的最大公约数 $(GCD)$ 而 $lcm(a, b)$ 是 $(LCM)$ 时，他有些惊讶。他认为，既然 $LCM$ 和 $GCD$ 的乘积存在，那么考虑它们的商可能会很有趣： $F(a,b)=\frac{lcm(a, b)}{gcd(a, b)}$ .

例如，他取 $a = 2$ 和 $b = 4$ ，计算 $F(2, 4) = \frac{4}{2} = 2$ ，得到一个质数(如果一个数只能被 $1$ 和它半身整除，它就是质数)！现在他认为，如果 $a \lt b$ 并且 $F(a, b)$ 是质数，那么 $F(a, b)$ 就是一个有趣的比。

由于他刚刚开始学习数论，他需要您的帮助来计算--有多少对不同的数在 $1 \leq a \lt b \leq n$ 的前提下使得 $F(a, b)$ 是一个有趣的比。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \leq t \leq 10^3$ )。测试用例说明如下。

每个测试用例的单行包含一个整数 $n$ 。

输出格式

对于每个测试用例，输出满足 $1 \leq a \lt b \leq n$ 的成对有趣比率 $F(a, b)$ 的数量。

样例1

input

4
5
10
34
10007

output

4
11
49
24317

限制与约定

对于$40\%$的数据，保证所有测试用例的 $n$ 之和不超过 $100$ 。

对于$100\%$的数据，保证 $2 \le n \le 10^7$ 并且所有样例的 $n$ 之和不超过 $10^7$ 。

• 时间限制: $2 s$
• 空间限制: $256 MB$