P17433 [LBA-OI R5 C] 卿即终解

::::align{center} 卿即终解，数证初心 :::: 高三那年，苏晚在草稿纸上写下三个求和号和一个最大公约数。多年后，林默重新敲下代码，等屏幕给出一个数字——那是隔了十一年的回音。

给定 $n$，求 $\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}$。

**本题目有多组测试数据。** 第一行一个整数 $T$，表示数据总数。 接下来 $T$ 行，每行一个整数 $n$。

输出 $T$ 行，每行一个整数，表示答案。

对于 $100\%$ 的数据：$T\le 3000$，$1\le n\le3\times 10^7$。 ::cute-table{tuack} | 测试点编号 | $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$ |