P6860 Chinese Chess and the Knight

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.

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

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

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$ | $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$ | $15$ | | $4$ | $11\sim 15$ | $n\leq 10^7, T\leq 5$ | $15$ | | $5$ | $16\sim 18$ | $n\leq 10^9, T\leq 5$ | $15$ | | $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