A15338. Madoka and Strange Thoughts

Madoka is a very strange girl, and therefore she suddenly wondered how many pairs of integers $(a, b)$ exist, where $1 \leq a, b \leq n$ , for which $\frac{\operatorname{lcm}(a, b)}{\operatorname{gcd}(a, b)} \leq 3$ .

In this problem, $\operatorname{gcd}(a, b)$ denotes [the greatest common divisor](<https://en.wikipedia.org/wiki/Greatest_common_divisor >) of the numbers $a$ and $b$ , and $\operatorname{lcm}(a, b)$ denotes [the smallest common multiple](<https://en.wikipedia.org/wiki/Least_common_multiple >) of the numbers $a$ and $b$ .

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$ ).

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

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.