最近，Stump 突然领悟到 $\sum_{k=1}^n \mu^2(k) = \sum_{k=1}^n \mu(k) \lfloor \frac{n}{k^2} \rfloor$，这让 Yoshinow2001 整整震惊了一年！！

上述 $\mu$ 为莫比乌斯函数 $\mu(n)$：如果 $n$ 包含平方因子（即存在正整数 $a > 1$ 使得 $a^2|n$），则 $\mu(n) = 0$。否则，设 $n$ 的质因数分解为 $n = p_1 \cdot p_2 \cdot \dots \cdot p_k$，则 $\mu(n) = (-1)^k$。例如，$\mu(1) = 1, \mu(2) = \mu(3) = -1$。

回想一下，$\ln(n)$ 表示以 $e = \sum_{n=0}^\infty \frac{1}{n!} \approx 2.71828$ 为底的 $n$ 的对数。

现在 Yoshinow2001 非常愤怒，并提出了一个问题！令 $$S(n) = \sum_{d|n} \mu\left(\frac{n}{d}\right) \ln(d)$$

你需要计算： $$e^{S(n)} \pmod{998244353}$$

Stump 看到这个公式时感到非常恐惧！现在他请求你用心去感受它！

输入格式

第一行输入一个正整数 $T(1 \le T \le 2000)$，表示测试用例的数量。 下一行包含总共 $T$ 个整数，每个整数对应题目中描述的 $n$，其中 $1 \le n \le 10^{18}$。

输出格式

对于每个测试用例，输出一个表示答案模 $998244353$ 的整数，用空格分隔。

样例

输入格式 1

3
1 2 3

输出格式 1

2
1 2 3