Description

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

的值。

Input Format

本题含有多组数据。

输入的第一行为一个整数，表示数据组数 $T$。

接下来 $T$ 行，每行一个整数 $n$，表示一个询问。

Output Format

输出共 $T$ 行。

对于每组询问，输出一行一个整数，即

$$\left ( \sum_{a=1}^n\sum_{b=1}^np(a,b) \right )\bmod\ 2^{64}$$

的值。

3
2
3
4

2
4
8

Hint

样例解释：当 $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 优化开关。