象棋与马

Amazing John 做了一个梦，梦到他下辈子是个象棋大师。 因为人与人之间是不能一概而论的，马与象之间也不能相提并论。 Amazing John 在极度愤怒的情况下创造了一种新的棋：马棋。 “啊这，不会真有人不会下这种棋吧？” 现在他想请你来体验一下这种新棋。

Amazing John 有一个无限大的棋盘来下马棋。 有一个马最开始在 $(0,0)$，它的每一步可以走一个 $a\times b$ 的矩形（ 即能够从$(x,y)$到达 $(x\pm a,y\pm b)$ 或 $(x\pm b,y\pm a)$ ）。 若马通过上述移动方式可以到达棋盘中任意一个点，那么 $p(a,b)=1$，否则 $p(a,b)=0$。 现在 Amazing John 给你 $T$ 组询问，每组询问他会给出一个正整数 $n$，他想知道 $$\left ( \sum_{a=1}^n\sum_{b=1}^np(a,b) \right )\bmod\ 2^{64}$$ 的值。

**本题含有多组数据。** 输入的第一行为一个整数，表示数据组数 $T$。 接下来 $T$ 行，每行一个整数 $n$，表示一个询问。

输出共 $T$ 行。 对于每组询问，输出一行一个整数，即 $$\left ( \sum_{a=1}^n\sum_{b=1}^np(a,b) \right )\bmod\ 2^{64}$$ 的值。

3
2
3
4

2
4
8

样例解释：当 $n=3$ 时，值为 $1$ 的有 $p(1,2),p(2,1),p(2,3),p(3,2)$。 **本题开启Subtask** |子任务|数据点|数据范围|分数| |-|-|-|- |$1$|$1$|$n\leq 10,T\leq5$|$5$| |$2$|$2\sim 5$|$n\leq 3000,T\leq5$|$15$| |$3$|$6\sim 10$|$n\leq 10^5,T\leq 5$|$15$| |$4$|$11\sim 15$|$n\leq 10^7,T\leq5$|$15$| |$5$|$16\sim 18$|$n\leq10^9,T\leq 5$|$15$| |$6$|$19\sim 25$|$n\times T\leq 10^{11},T\leq 5$|$35$| 注 1：对于 $n\times T\geq 5*10^{10}$ 的数据点，时限为 **4s** ，其余均为 **2.5s** 。且对于所有数据点，空间限制为 **500MB** 。 注 2：输出答案 $\bmod\ 2^{64}$ 即对 **64位无符号整数** 自然溢出。 本题开启 -O2 优化开关。