Background

Problem Description

This problem guarantees that the testdata is generated randomly.

There is a complete graph with $n$ vertices, numbered $1,2,\ldots,n$. Between vertices $i$ and $j$, there is an undirected edge with weight $\mathrm{lcm}(i,j)+\mathrm{gcd}(i,j)$.

Please find the total weight of the maximum spanning tree of this graph, modulo $2^{32}$.

Input Format

This problem contains multiple test cases. The first line contains an integer $T$, representing the number of test cases.

The next $T$ lines each contain one integer $n$, representing the number of vertices.

Output Format

Output $T$ lines. Each line contains one integer, representing the answer for one test case.

9
10
1000
100000
10000000
1000000000
100000000000
10000000000000
1000000000000000
100000000000000000

422
499008694
4172096327
3128649679
2692599804
194024000
2969759816
505684415
3052141644

Hint

There are subtasks.

Constraints

• For $5\%$ of the testdata, $T=1,n\leq 2000$.
• For $15\%$ of the testdata, $T=1,n\leq 10^6$.
• For $30\%$ of the testdata, $T=1,n\leq 10^8$.
• For $50\%$ of the testdata, $T=1,n\leq 10^{10}$.
• For $75\%$ of the testdata, $T=1,n\leq 10^{15}$.
• For $100\%$ of the testdata, $T\leq 10,n\leq 10^{18}$.

A fast Pollard_Rho prime factorization code is provided in the distributed files.

Translated by ChatGPT 5