背景

::::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$ 行，每行一个整数，表示答案。

5
1
2
51
1000
114514

1
35
3188479762
171666321110333776
14226039676014353747

提示

对于 $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$ |