Rikka with APSP

Problem Description

Input

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}$.

Output

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

Sample Input

3

4

10

100

Sample Output

16

243

190371

Source

2018 Multi-University Training Contest 9