Counting Stairs

Time limit3sMemory limit512 MB

Summary

Count symmetric stairs (partitions of n into distinct parts) with n cubes, modulo 998244353, for up to 1e4 queries with n up to 2e5.

Level: Hard8 of 10
Topics: Dynamic programming, Math, Combinatorics, Number theory
Solved: No attempts yet

Problem

Remember Barney from problem B? Barney's older sister Cecilia often watches him play with his set of cubes. She also joins Barney in his games and prevails most of the time, shaking his confidence on a daily basis.

One day Cecilia noticed Barney struggling to build a symmetric stair with his $n$ cubes. She immediately told him she could not just build a symmetric stair, but even calculate the number of different symmetric stairs consisting of $n$ cubes! Can you?

Recall that a symmetric stair consists of one or more towers of cubes, where the heights of towers are non-increasing from left to right, and is symmetric with respect to the line $x = y$ (where the $x$ -axis is horizontal and oriented to the right, and the $y$ -axis is vertical and oriented upwards). For a more detailed explanation, please refer to problem B statement.

The number of different symmetric stairs can be quite large, so you need to calculate it modulo $998\,244\,353$ .

Input

The input contains multiple test cases.

The first line of the input contains a single integer $t$ — the number of test cases ( $1 \le t \le 10^4$ ). Each of the following $t$ lines contains a single integer $n_i$ — the number of cubes in the $i$ -th test case ( $1 \le n_i \le 2 \cdot 10^5$ ).

Output

For each test case, output a line with a single integer — the number of symmetric stairs with exactly $n_i$ cubes, modulo $998\,244\,353$ .

Hint

All different symmetric stairs with $n = 17$ cubes are shown below:

Examples1

Example 1
Input
```
4
3
5
17
25
```
Expected output
```
1
1
5
12
```