Problem Description

Recently, Stump felt $\sum_{k=1}^n \mu^2(k)=\sum_{k=1}^n \mu(k)\lfloor\frac{n}{k^2}\rfloor$ with his heart immediately, which shocked Yoshinow2001 for a whole year!!

The above $\mu$ is $\textbf{Möbius function}$ $\mu(n)$: If $n$ contain square factor (i.e. there are positive integers $a > 1$ makes $a^2|n$ ) then the $\mu (n) = 0$. Otherwise, might as well set decomposition of prime factors of $n$ type $n=p_1\cdot p_2 \dots \cdot p_k$, then $\mu (n) = (-1)^k$. For example, $\mu(1)=1,\mu(2)=\mu(3)=-1$.

Recall that $\ln(n)$ denotes the logarithm of $n$ with base $e=\sum_{n=0}^{\infty}\frac{1}{n!}\approx 2.71828$.

Now Yoshinow2001 is furious and pulls out a question! Let

$$\begin{aligned}S(n)=\sum_{d|n}\mu(\frac{n}{d})\ln(d)\end{aligned}$$

You need to calculate:

$$e^{S(n)}\bmod 998244353$$

Stump was horrified when he saw the formula! Now he asks you to feel it with your heart for him!

Input

The first line of input is a positive integer $T(1\leq T\leq 2000)$ representing the number of data cases.

The next line has a total of $T$ integers, each of which corresponds to $n$ as described in the problem, where $1\leq n\leq 10^{18}$.

Output

For each testcase, output an integer representing the answer $\bmod \ 998244353$, separated by a space.

3
1 2 3

1 2 3