LCMSUM 1

Problem Description

$T$ queries. Each query gives an $n$; output $\left(\sum_{i=1}^n [i,n]\right) \bmod {2^{60}}$, where $[i,n]$ denotes $\operatorname{lcm}(i,n)$.

Input Format

The first line contains one integer $T$. The following $T$ lines each contain one integer representing the number $n$.

Output Format

One integer per line: the answer.

Sample Input

3
10
123
1234567

Sample Output

320
706512
933390306503591194

Constraints

For all data, it is guaranteed that $T\leq 10^5$, $1\leq n\leq 10^7$.

Hint

• Rewrite $\sum_{i=1}^n \operatorname{lcm}(i,n) = n\sum_{i=1}^n \frac{i}{\gcd(i,n)}$ and group by $d=\gcd(i,n)$; this reduces to a divisor sum involving Euler's totient function. Precompute $\varphi$ with a linear sieve, then answer each query in $O(\sqrt n)$ (or faster with prefix sums), taking the modulus $2^{60}$ with 64-bit unsigned arithmetic.