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.