你在参加一场考试，并不断思考如何计算最大公约数。你竭尽全力回忆起 $\gcd(x, y)$ 是同时整除 $x$ 和 $y$ 的最大整数 $d \ge 1$。你模糊地记得在某次讲座中提到过类似的内容。唉，即使你的大脑在课上成功记录了任何零星的信息，它们现在也早已消失，被《巫师 Gebyte》的冒险故事以及《Peaky Byters》的最新剧集所取代。

你从黑板上的 $x$ 和 $y$ 开始……然后你计算了一些之前写下的数字的减法结果……？你试图赶走一个不愉快的想法，即这会不会像去年的中位数问题一样收场……还是这仅仅是你的噩梦之一？

基于你对讲座模糊的记忆，你想出了以下算法。你从写在黑板上的数字 $x$ 和 $y$ 开始。在每一步中，你可以选择黑板上已经存在的任意两个数字 $a$ 和 $b$，并写下 $c = 2a - b$，前提是 $c > 0$。对于数对 $(x, y)$，算法的结果是在重复上述过程若干次（可能为零次）后，黑板上能写出的最小数字。

在检查了几个测试用例后，你的算法看起来很有希望。例如，对于数对 $(10, 14)$，第一步中你可以写下的数字之一是 $6$（因为 $2 \cdot 10 - 14 = 6$），而在下一步中你可以写下 $2$（因为 $2 \cdot 6 - 10 = 2$）。另一方面，可以证明无法得到 $1$，因此该算法的答案是正确的。不幸的是，对于 $(10, 16)$，你所能得到的最小数字是 $4$，而正确答案是 $2$。有些不对劲……

对于给定的 $n$，确定有多少对 $(x, y)$（满足 $1 \le x < y \le n$），使得你的算法返回了正确的 $\gcd(x, y)$ 值 $^1$。

请注意，本题的内存限制较低，为 8MB。

输入格式

输入的第一行包含测试用例的数量 $z$ ($z \ge 1$)。接下来是各测试用例的描述。

每个测试用例仅包含一行，包含一个整数 $n$ ($n \ge 2$)，其含义如题目描述中所述。

数据范围

每个输入文件将属于以下三组之一：

• $z \le 3000, n \le 10^6$
• $z = 30, n \le 10^9$
• $z = 3, n \le 10^{11}$

输出格式

对于每个测试用例，输出一个整数，表示我们正在寻找的数对数量。

$^1$ 特别地，如果 $\gcd(x, y) = x$，则我们认为该算法工作正常，因为 $x$ 在开始时就已经写在黑板上了。

样例

样例输入 1

3
2
5
14

样例输出 1

1
9
62