Problem Description

Consider a triangle of integers, denoted by $T$. The value at $(r,c)$ is denoted by $T_{r,c}$, where $1 \le r$ and $1 \le c \le r$. If the greatest common divisor of $r$ and $c$ is exactly $1$, $T_{r,c} = c$, or $0$ otherwise.

Now, we have another triangle of integers, denoted by $S$. The value at $(r,c)$ is denoted by $S_{r,c}$, where $1 \le r$ and $1 \le c \le r$. $S_{r,c}$ is defined as the summation $\sum_{i=c}^{r} T_{r,i}$.

Here comes your turn. For given positive integer $k$, you need to calculate the summation of elements in $k$-th row of the triangle $S$.

Input Format

The first line of input contains an integer $t (1 \le t \le 10000)$ which is the number of test cases. Each test case includes a single line with an integer $k$ described as above satisfying $2 \le k \le 10^8$.

Output Format

For each case, calculate the summation of elements in the $k$-th row of $S$, and output the remainder when it divided by $998244353$.

2
2
3

1
5