P17433 [LBA-OI R5 C] You Are the Ultimate Solution

::::align{center} 卿即终解，数证初心 :::: In the final year of high school, Su Wan wrote three summation symbols and a greatest common divisor on scratch paper. Many years later, Lin Mo typed the code again and waited for the screen to output a number—that was an echo after eleven years.

Given $n$, compute $\left(\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{n}{\sum\limits_{k=1}^{n}{i\cdot j\cdot k\cdot\gcd(i,j,k)}}}\right) \bmod 2^{64}$.

**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$.

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

Constraints for $100\%$ of the data: $T\le 3000$, $1\le n\le 3\times 10^7$. ::cute-table{tuack} | Test Point ID | $T$ | $n$ | | :---: | :---: | :---: | | $1,2$ | $=5$ | $\le 300$ | | $3,4$ | $\le 3000$ | $\le 100$ | | $5,6$ | ^ | $\le 3000$ | | $7 \sim 10$ | ^ | $\le 10^4$ | | $11 \sim 14$ | ^ | $\le 10^6$ | | $15 \sim 20$ | ^ | $\le 3 \times 10^7$ | Translated by ChatGPT 5