Madoka and Strange Thoughts

Description:

Input:

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Description of the test cases follows.

The first and the only line of each test case contains the integer $$$n$$$ ($$$1 \le n \le 10^8$$$).

Output:

For each test case output a single integer — the number of pairs of integers satisfying the condition.

Sample Input:

6
1
2
3
4
5
100000000

Sample Output:

1
4
7
10
11
266666666

Note:

For $$$n = 1$$$ there is exactly one pair of numbers — $$$(1, 1)$$$ and it fits.

For $$$n = 2$$$, there are only $$$4$$$ pairs — $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$ and they all fit.

For $$$n = 3$$$, all $$$9$$$ pair are suitable, except $$$(2, 3)$$$ and $$$(3, 2)$$$, since their $$$\operatorname{lcm}$$$ is $$$6$$$, and $$$\operatorname{gcd}$$$ is $$$1$$$, which doesn't fit the condition.