CF2238B Crimson Triples

Chills run down your spine... — Terraria After summoning the next boss — The Brain of Cthulhu, you noticed that it surrounds itself with $ n $ eyes, numbered from $ 1 $ to $ n $ . In one attack, The Brain of Cthulhu chooses a triple of eyes (not necessarily distinct) with numbers $ (a, b, c) $ . The triple of eyes is called crimson if and only if the following property holds: $ \gcd $ $ ^{\text{∗}} $ $ (\operatorname{lcm} $ $ ^{\text{†}} $ $ (a, b), \operatorname{lcm}(b, c)) = \gcd(a, c) $ , To defeat the boss, you want to know how many ways The Brain of Cthulhu can choose a crimson triple of eyes. The triples of eyes $ (a_1, b_1, c_1) $ and $ (a_2, b_2, c_2) $ are considered different if $ a_1 \neq a_2 $ , or $ b_1 \neq b_2 $ , or $ c_1 \neq c_2 $ . $ ^{\text{∗}} $ $ \gcd(x, y) $ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $ x $ and $ y $ . $ ^{\text{†}} $ $ \operatorname{lcm}(x, y) $ denotes the [least common multiple (LCM)](https://en.wikipedia.org/wiki/Least_common_multiple) of integers $ x $ and $ y $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 1000 $ ). The description of the test cases follows. The only line of each test case contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of eyes of The Brain of Cthulhu. It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output one integer — the number of ways to choose a crimson triple of eyes.

In the first test case, there is $ 1 $ possible crimson triple: $ (1, 1, 1) $ . In the second test case, there are $ 5 $ possible crimson triples: $ (1, 1, 1) $ , $ (1, 1, 2) $ , $ (2, 1, 1) $ , $ (2, 1, 2) $ , $ (2, 2, 2) $ .