Background

::::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.

Problem Description

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

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

Output Format

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

5
1
2
51
1000
114514

1
35
3188479762
171666321110333776
14226039676014353747

Hint

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