Madoka and Strange Thoughts

题意翻译

### 题目描述 给定一个整数 $n$，求出有多少组满足条件的 $\left ( a, b\right) (1 \le a, b \le n)$，使得 $\frac{\operatorname{lcm}(a, b) }{\gcd(a, b) } \le 3$。 在该题目中，$\gcd(a, b)$ 指的是 $a$ 和 $b$ 的最大公约数，而 $lcm(a, b)$ 指的是 $a$ 和 $b$ 的最小公倍数。 ### 输入格式 第一行输入一个整数 $t(1 \le t \le 10^4)$，代表测试数据的组数。 接下来 $t$ 行，每行一个整数 $n(1 \le n \le 10^8)$，代表题目中的整数 $n$。 ### 输出格式 对于每个测试数据，输出一个整数，代表满足条件的 $(a, b)$ 的数量。

题目描述

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.

输入输出样例

输入样例 #1

6
1
2
3
4
5
100000000

输出样例 #1

1
4
7
10
11
266666666

说明

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$，求出有多少组满足条件的 $(a, b)(1 \le a, b \le n)$，使得 $\frac{\operatorname{lcm}(a, b)}{\gcd(a, b)} \le 3$。其中 $\gcd(a, b)$ 表示 $a$ 和 $b$ 的最大公约数，$\lcm(a, b)$ 表示 $a$ 和 $b$ 的最小公倍数。

输入格式：第一行输入一个整数 $t(1 \le t \le 10^4)$，代表测试数据的组数。接下来 $t$ 行，每行一个整数 $n(1 \le n \le 10^8)$，代表题目中的整数 $n$。

输出格式：对于每个测试数据，输出一个整数，代表满足条件的 $(a, b)$ 的数量。题目大意：给定一个整数 $n$，求出有多少组满足条件的 $(a, b)(1 \le a, b \le n)$，使得 $\frac{\operatorname{lcm}(a, b)}{\gcd(a, b)} \le 3$。其中 $\gcd(a, b)$ 表示 $a$ 和 $b$ 的最大公约数，$\lcm(a, b)$ 表示 $a$ 和 $b$ 的最小公倍数。 输入格式：第一行输入一个整数 $t(1 \le t \le 10^4)$，代表测试数据的组数。接下来 $t$ 行，每行一个整数 $n(1 \le n \le 10^8)$，代表题目中的整数 $n$。 输出格式：对于每个测试数据，输出一个整数，代表满足条件的 $(a, b)$ 的数量。