Time Limit: 10000/5000 MS (Java/Others)

Memory Limit: 153428/153428 K (Java/Others)

Given an integer N, consider all multi-sets of positive integers such that their sum is N.

For example, if N =3, there are three possible multi-sets {1, 1, 1}, {1, 2}, {3}.

For each multi-set calculate the cube of its size and output the sum of all these values modulo 998244353.

For example, if N =3, there are three possible multi-sets {1, 1, 1}, {1, 2}, {3}.

For each multi-set calculate the cube of its size and output the sum of all these values modulo 998244353.

The first line of input contains an integer T (1<= T <=10000), the number of test cases.

Each test case contains a single integer N (1<= N<=100000).

Each test case contains a single integer N (1<= N<=100000).

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

1 9 36 513842114For the 1st case, the only possible multi-set is {1}. So the answer is 1^3=1. For the 2nd case, there are 2 possible multi-sets. {1, 1}, {2}. So the answer is 2^3+1^3=9. For the 3rd case, there are 3 possible multi-sets. {1, 1, 1}, {1, 2}, {3}. So the answer is 3^3+2^3+1^3=36.Hint

提交代码