问题 G: Guess

Recently, Stump felt ∑k =1n μ^2 (k) = ∑k = 1n μ(k) ⌊k 2n⌋ with his heart immediately, which shocked Yoshinow2001 for a whole year!!

The above $\mu$ is $\text{Mo¨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=p1⋅p2⋯⋅pk, then μ(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=∑n=0∞n!1≈2.71828.

Now Yoshinow2001 is furious and pulls out a question! Let

S(n)=d∣n∑μ(dn)ln(d)

You need to calculate:

eS(n)mod998244353

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

The first line of input is a positive integer $T(1\le T\le 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\le n\le 10^18$.