Madoka and Strange Thoughts (Codeforces 1717A)
Tags: Math, number theory

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

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.

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.

Sample Inputs:
6
1
2
3
4
5
100000000

Sample Outputs:
1
4
7
10
11
266666666

Solution (Python):
for n in [*map(int, open(0))][1:]:
    print((n // 3 + n // 2) * 2 + n)

Solution (Python):
import sys
n = int(sys.stdin.readline())
for i in range(n):
    b = int(sys.stdin.readline())
    print(b + b // 2 * 2 + b // 3 * 2)

Solution (Python):
class Solution:

    def __init__(self):
        pass

    def solve(self):
        t = int(input())
        result = []
        for i in range(t):
            n = int(input())
            count = n + n // 2 * 2 + n // 3 * 2
            result.append(count)
        for x in result:
            print(x)
if __name__ == '__main__':
    sol = Solution()
    sol.solve()