[Solution] Madoka and Strange Thoughts Codeforces Solution

A. Madoka and Strange Thoughts

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 (𝑎,𝑏)$(a,b)$ exist, where 1≤𝑎,𝑏≤𝑛$1\le a,b\le n$, for which lcm(𝑎,𝑏)gcd(𝑎,𝑏)≤3$\frac{\mathrm{lcm}(a,b)}{\gcd (a,b)}\le 3$.

In this problem, gcd(𝑎,𝑏)$\gcd (a,b)$ denotes the greatest common divisor of the numbers 𝑎$a$ and 𝑏$b$, and lcm(𝑎,𝑏)$\mathrm{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≤𝑡≤104$1\le t\le {10}^4$) — the number of test cases. Description of the test cases follows.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

The first and the only line of each test case contains the integer 𝑛$n$ (1≤𝑛≤108$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 𝑛=1$n=1$ there is exactly one pair of numbers — (1,1)$(1,1)$ and it fits.

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

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