E. 有趣的比值
每个测试点时间限制：2 秒
内存限制：256 兆字节

最近，在 IT 校园 "NEIMARK" 的训练营中，Misha 学习了一个新主题 —— 欧几里得算法。

他有些惊讶地发现：$a \cdot b = \operatorname{lcm}(a, b) \cdot \gcd(a, b)$，其中 $\gcd(a, b)$ 是 $a$ 和 $b$ 的最大公约数，$\operatorname{lcm}(a, b)$ 是 $a$ 和 $b$ 的最小公倍数。Misha 认为既然 $\operatorname{lcm}$ 和 $\gcd$ 的乘积存在，那么考虑它们的商可能会很有趣：

$$F(a, b) = \frac{\operatorname{lcm}(a, b)}{\gcd(a, b)} $$

例如，他取 $a = 2$ 和 $b = 4$，计算出 $F(2, 4) = \frac{4}{2} = 2$，得到了一个质数（一个数如果恰好有两个约数，则称之为质数）！现在，如果 $a < b$ 且 $F(a, b)$ 是质数，他就认为 $F(a, b)$ 是一个有趣的比值。

由于 Misha 刚刚开始学习数论，他需要你的帮助来计算 —— 有多少对不同的数 $(a, b)$ 满足 $F(a, b)$ 是一个有趣的比值，并且 $1 \le a < b \le n$？

---

输入格式

每个测试文件包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。每个测试用例的描述如下：

每个测试用例只有一行，包含一个整数 $n$（$2 \le n \le 10^7$）。

保证所有测试用例的 $n$ 之和不超过 $10^7$。

---

输出格式

对于每个测试用例，输出满足 $1 \le a < b \le n$ 且 $F(a, b)$ 为质数的有序对 $(a, b)$ 的数量。

---

示例输入

4
5
10
34
10007

示例输出

4
11
49
24317