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

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.