CF1717A.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 of the numbers $a$ and $b$, and $\operatorname{lcm}(a, b)$ denotes the smallest common multiple of the numbers $a$ and $b$.

魔笛是一个非常奇怪的女孩，因此她突然想到：满足 $1 \leq a, b \leq n$ 的整数对 $(a, b)$ 有多少个，使得 $\frac{\operatorname{lcm}(a, b)}{\operatorname{gcd}(a, b)} \leq 3$？

在本题中，$\operatorname{gcd}(a, b)$ 表示整数 $a$ 和 $b$ 的最大公约数，而 $\operatorname{lcm}(a, b)$ 表示整数 $a$ 和 $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$).

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例仅有一行，包含一个整数 $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.

当 $n = 1$ 时，恰好存在一对数——$(1, 1)$，且它满足条件。

当 $n = 2$ 时，仅有 $4$ 对数——$(1, 1)$、$(1, 2)$、$(2, 1)$、$(2, 2)$，它们均满足条件。

当 $n = 3$ 时，全部 $9$ 对数中，除 $(2, 3)$ 和 $(3, 2)$ 外均满足条件，因为它们的 $\operatorname{lcm}$ 为 $6$，而 $\operatorname{gcd}$ 为 $1$，不满足题目条件。