## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Madoka and Strange Thoughts Codeforces Solution

time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Madoka is a very strange girl, and therefore she suddenly wondered how many pairs of integers $\left(a,b\right)$ exist, where $1\le a,b\le n$, for which $\frac{\mathrm{lcm}\left(a,b\right)}{\mathrm{gcd}\left(a,b\right)}\le 3$.

In this problem, $\mathrm{gcd}\left(a,b\right)$ denotes the greatest common divisor of the numbers $a$ and $b$, and $\mathrm{lcm}\left(a,b\right)$ 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.

Solution Click Below:-  👉
👇👇👇👇👇

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 — $\left(1,1\right)$ and it fits.

For $n=2$, there are only $4$ pairs — $\left(1,1\right)$$\left(1,2\right)$$\left(2,1\right)$$\left(2,2\right)$ and they all fit.

For $n=3$, all $9$ pair are suitable, except $\left(2,3\right)$ and $\left(3,2\right)$, since their $\mathrm{lcm}$ is $6$, and $\mathrm{gcd}$ is $1$, which doesn't fit the condition.