给定一个整数 $N$，考虑所有正整数的多重集，使得它们的和为 $N$。 例如，若 $N = 3$，则有三种可能的多重集：$\{1, 1, 1\}$，$\{1, 2\}$ 和 $\{3\}$。 对于每个多重集，计算其大小的立方，并输出所有这些值的和，结果对 $998\,244\,353$ 取模。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量 ($1 \le T \le 10^5$)。 每个测试用例包含一行，为一个整数 $N$ ($1 \le N \le 10^5$)。

输出格式

对于每个测试用例，输出一行，包含一个整数：问题的答案。

样例

输入 1

4
1
2
3
100000

输出 1

1
9
36
513842114

说明

对于第一个样例，唯一可能的多重集是 $\{1\}$。因此答案为 $1^3 = 1$。 对于第二个样例，有两种可能的多重集：$\{1, 1\}$ 和 $\{2\}$。因此答案为 $2^3 + 1^3 = 9$。 对于第三个样例，有三种可能的多重集：$\{1, 1, 1\}$，$\{1, 2\}$ 和 $\{3\}$。因此答案为 $3^3 + 2^3 + 1^3 = 36$。