Infinite Chessboard Knight Reachability

Amazing John has an infinite chessboard. A knight starts at the origin \((0,0)\) and its move is defined by two positive integers \(a\) and \(b\). In one move, the knight can jump from \((x,y)\) to any one of the eight positions:

\[ (x \pm a,\; y \pm b) \quad \text{or} \quad (x \pm b,\; y \pm a), \]

For a given pair \((a,b)\), define \[ p(a,b)=\begin{cases} 1, & \text{if the knight can reach any cell on the board,}\\ 0, & \text{otherwise.} \end{cases} \] It can be shown that the knight can visit every cell of the board if and only if \(\gcd(a,b)=1\).

Now, Amazing John will give you \(T\) queries. In each query, you are given a positive integer \(n\). For each query, compute \[ S(n) = \left( \sum_{a=1}^{n} \sum_{b=1}^{n} p(a,b) \right) \bmod 2^{64} \quad = \quad \left( \#\{(a,b)\;:\; 1\le a,b\le n,\; \gcd(a,b)=1\} \right) \bmod 2^{64}. \]

inputFormat

The first line contains an integer \(T\) \((1 \le T)\) indicating the number of queries. Each of the following \(T\) lines contains a single positive integer \(n\) \((1 \le n)\). It is guaranteed that \(n\) is such that the solution can be computed within the allowed time.

outputFormat

For each query, output a single line containing the value of \(S(n)\) modulo \(2^{64}\).

sample

1
1

1