APSP (All Pair Shortest Path) is a basic problem in graph theory.

Since solving APSP for arbitrary graphs is not a simple task, Rikka wants to start with some particular graphs.

At first, Rikka has $n$ vertices without any edges. And then for each pair of vertices $(i,j)(i<j)$, Rikka links an undirected edge between them with length $f(i,j)$. The value of $f(i,j)$ is equal to the minimum positive integer $k$ which satisfies $ijk$ is a square number. (It is clear that $f(i,j)$ always exists because $ij(ij)$ must be a square number)

For example, if $n=4$, the adjacency matrix of the graph will be:
\begin{align*}
\begin{bmatrix}
/ & 2 & 3 & 1 \\
2 & / & 6 & 2 \\
3 & 6 & / & 3 \\
1 & 2 & 3 & / \\
\end{bmatrix}
\end{align*}

Let $d(i,j)$ be the length of the shortest path between vertex $i,j$. And now Rikka wants you to calculate:
$$\sum_{i=1}^n \sum_{j=i+1}^{n} d(i,j)$$

The first line contains one single integer $t(1 \leq t \leq 50)$, the number of the testcases.

For each testcase, the first line contains exactly one integer $n(1 \leq n \leq 10^{10})$.

The input guarantees that there are at most $3$ testcases with $n > 10^{8}$.

For each testcase, output a single integer, the answer modulo $998244353$.