Background

Amazing John had a dream that in his next life he would be a master of Chinese chess.

Because people cannot be generalized, neither can knights and bishops be compared as the same.

In extreme anger, Amazing John invented a new kind of chess: Knight Chess.

“Come on, no one actually can’t play this game, right?”

Now he wants to invite you to experience this new game.

Problem 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