31605번 - Zig-zag 다국어

문제

Zack’s Zergonomics Zegree has taught him that the optimal way to display items in a store is to stack them into a zig-zag pattern.

Zack needs to display $n$ boxes lined up on the storefront, each one containing an action figure. These boxes can be stacked on top of one another, and they are identical and indistinguishable from each other. His goal is to decide the number of stacks, and then stack up the boxes such that each stack is non-empty, and the numbers of boxes in the stacks form a zig-zag sequence.

Formally, if there are $s$ ($s ≥ 1$) stacks numbered 1ドル$ to $s$ from left to right, and stack $i$ contains $a_i$ boxes, then the following conditions must be satisfied:

• $a_i ≥ 1$ for each $i$ from 1ドル$ to $s,ドル
• $a_1 + a_2 + \dots + a_s = n,ドル and
• at least one of the following is true:
  • $a_1 < a_2 > a_3 < a_4 > \dots,ドル or
  • $a_1 > a_2 < a_3 > a_4 < \dots$

For example, for $n = 6,ドル there are 12ドル$ ways as illustrated by Figure M.1.

Figure M.1: All 12ドル$ possible ways for $n = 6$.

Find the number of different ways Zack can stack $n$ boxes modulo 998ドル,円 244,円 353$.

Two ways are considered the same if and only if the number of stacks is the same, and pairs of stacks at the same positions have the same number of boxes.

입력

The first line of input contains one integer $t$ (1ドル ≤ t ≤ 300,円 000$) representing the number of test cases. After that, $t$ test cases follow. Each of them consists of a single line containing one integer $n$ (1ドル ≤ n ≤ 300,円 000$).

출력

For each test case, output an integer representing the number of different ways to stack $n$ boxes modulo 998ドル,円 244,円 353$.

제한

힌트