最近,Misha在IT校园“NEIMARK”训练营学习了一个新课题——欧几里得算法。
当他意识到 $$$a \cdot b = lcm(a, b) \cdot gcd(a, b)$$$ 时,他有些惊讶,其中 $$$gcd(a, b)$$$ — 是数字 $$$a$$$ 和 $$$b$$$ 的最大公约数 (GCD),而 $$$lcm(a, b)$$$ — 是最小公倍数(LCM)。 Misha 认为既然 LCM 和 GCD 的乘积存在,那么考虑它们的商可能会很有趣:$$$F(a,b)=\frac{lcm(a, b)}{gcd(a, b)}$$$。
例如,他取 $$$a = 2$$$ 和 $$$b = 4$$$,计算 $$$F(2, 4) = \frac{4}{2} = 2$$$ 并获得一个素数(如果一个数恰好有两个约数,则该数是素数)!现在,如果 $$$a \lt b$$$ 且 $$$F(a, b)$$$ 是质数,他认为 $$$F(a, b)$$$ 是一个有趣的比率。
由于 Misha 刚刚开始学习数论,他需要你的帮助来计算 — 有多少对不同的数字 $$$a$$$ 和 $$$b$$$ 使得 $$$F(a, b)$$$ 是一个有趣的比率,并且 $$$1 \leq a \lt b \leq n$$$?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10^3$$$)。测试用例的描述如下。
每个测试用例的一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^7$$$)。
保证所有测试用例的$$$n$$$总和不超过$$$10^7$$$。
输出
对于每个测试用例,输出满足 $$$1 \leq a \lt b \leq n$$$ 的有趣比率 $$$F(a, b)$$$ 的数量。
示例
输入复制
45103410007
输出复制
4 11 49 24317