Description

ACM竞赛中常见的一部分就是数论啦，集训队的同学刚刚打完codeforce(CF)，大家都好想出去玩，但是队长说：不如我们用一道有趣的数学题收尾吧~

队长：我昨天在想这些数字好神奇呀，你们能不能快速的输出点自然数求和的规律呢？ 队员：这个很简单呀不就是1,3,6,10,15...

听见队员直接说了起来，喜欢挑战的队长觉得问题不能这么简单

队长：我说的是其他性质啦，比方说咱们可以看看自然数的平方数&立方数的连续和~

队长说完便打出了公式，等下他会提供一些数字n，成员们需要计算下面的式子并输出：

这样看来答案是个小数了，由于小数不好计算，还是需要把分数 $\frac p q$ 形式变换为整数形式，请将数字打印输出形式为 $(p \times q^{-1})\mod 998244353$。

Input Format

第一行 $t(1 \leq t \leq 10)$ 为测试数据组数​，对于每组数据：

每行包含一个整数 $n (1\leq n \leq 10^8)$。

Output Format

对于每组样例：

输出一个整数。

2
1
8​

1
499122202​

Hint

第一个样例 $(p \times q^{-1})\mod 998244353$ 中p=1, q = 1, q的逆元 $q^{-1}$ 还是 1 所以值为 1*1=1