Cube Summation

Given an integer $N$, consider all multi-sets of positive integers whose sum is $N$.

For example, when $N = 3$, there are three possible multi-sets: $\{1, 1, 1\}$, $\{1, 2\}$, and $\{3\}$.

For each multi-set, compute the cube of its size, and output the sum of these values modulo $998\,244\,353$.

The first line of input contains an integer $T$, the number of test cases ($1 \le T \le 10^5$).

Each test case consists of a single line containing a single integer $N$ ($1 \le N \le 10^5$).

For each test case, output a single line with the answer to the problem.

In the first case, the only possible multi-set is $\{1\}$. So the answer is $1^3 = 1$.

In the second case, there are two possible multi-sets: $\{1, 1\}$ and $\{2\}$. So the answer is $2^3 + 1^3 = 9$.

In the third case, there are three possible multi-sets: $\{1, 1, 1\}$, $\{1, 2\}$, and $\{3\}$. So the answer is $3^3 + 2^3 + 1^3 = 36$.