Description

Amazing John has an infinite chessboard to play Knight Chess.

There is a knight starting at $(0,0)$. Each move can be an $a\times b$ rectangle (that is, it can go from $(x,y)$ to $(x\pm a,y\pm b)$ or $(x\pm b,y\pm a)$).

If the knight can reach any point on the board using the moves above, then $p(a,b)=1$; otherwise $p(a,b)=0$.

Now Amazing John gives you $T$ queries. In each query, he gives a positive integer $n$, and he wants to know the value of

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

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

The next $T$ lines each contain an integer $n$, representing one query.

Output Format

Output $T$ lines in total.

For each query, output one integer, namely the value of

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

3
2
3
4

2
4
8

Hint

Sample explanation: when $n=3$, the cases with value $1$ are $p(1,2),p(2,1),p(2,3),p(3,2)$.

This problem enables Subtasks.

Subtask	Test Points	Constraints	Score
$1$		$n\leq 10, T\leq 5$	$5$
$2$	$2\sim 5$	$n\leq 3000, T\leq 5$	$15$
$3$	$6\sim 10$	$n\leq 10^5, T\leq 5$
$4$	$11\sim 15$	$n\leq 10^7, T\leq 5$
$5$	$16\sim 18$	$n\leq 10^9, T\leq 5$
$6$	$19\sim 25$	$n\times T\leq 10^{11}, T\leq 5$	$35$

Note 1: For test points with $n\times T\geq 5*10^{10}$, the time limit is 4 s; for all other test points, it is 2.5 s. For all test points, the memory limit is 500 MB.

Note 2: Outputting the answer $\bmod\ 2^{64}$ means using natural overflow of 64-bit unsigned integers.

This problem enables the -O2 optimization switch.

Translated by ChatGPT 5