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 containing an action figure. The boxes can be stacked on top of one another. They are identical and indistinguishable. He must decide the number of stacks, then stack the boxes so that each stack is non-empty and the stack sizes form a zig-zag sequence.

Formally, suppose there are $s$ ($s \ge 1$) stacks numbered $1$ to $s$ from left to right, and stack $i$ holds $a_i$ boxes. The following must hold:

• $a_i \ge 1$ for each $i$ from $1$ to $s$.
• $a_1 + a_2 + \dots + a_s = n$.
• At least one of the following is true:
  • $a_1 < a_2 > a_3 < a_4 > \dots$
  • $a_1 > a_2 < a_3 > a_4 < \dots$

For example, when $n = 6$, there are 12 ways, as shown in Figure M.1.

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

Two ways are the same if and only if they have the same number of stacks and the stacks at each position hold the same number of boxes.

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

The first line contains one integer $t$ ($1 \le t \le 300\,000$), the number of test cases. Each of the next $t$ lines contains one integer $n$ ($1 \le n \le 300\,000$).

For each test case, output the number of different ways to stack $n$ boxes, modulo $998\,244\,353$, on its own line.