P13627 [ICPC 2024 APC] Zig-zag

扎克的泽格工效学学位（Zergonomics Zegree）教会了他，在商店里展示物品的最佳方式是把它们堆叠成一种之字形图案。扎克需要将 $n$ 个装有可动人偶的盒子在店门口排成一列。这些盒子可以相互堆叠，并且它们是相同的、不可区分的。他的目标是决定要堆叠成的堆数，然后将盒子堆起来，使得每一堆都不是空的，并且各堆的盒子数量形成一个之字形序列。 形式上，如果有 $s$ ($s \ge 1$) 堆，从左到右编号为 $1$ 到 $s$，且第 $i$ 堆包含 $a_i$ 个盒子，那么必须满足以下条件： * 对于每个 $i$（从 $1$ 到 $s$），$a_i \ge 1$， * $a_1 + a_2 + \dots + a_s = n$，并且 * 以下至少一条为真： * $a_1 < a_2 > a_3 < a_4 > \dots$，或者 * $a_1 > a_2 < a_3 > a_4 < \dots$ 例如，对于 $n=6$，总共有 $12$ 种方式，如图 M.1 所示。  找出扎克可以用多少种不同的方式堆叠这 $n$ 个盒子，结果对 $998,244,353$ 取模。 两种方式被认为是相同的，当且仅当它们的堆数相同，并且在相同位置上的堆所含的盒子数量也相同。

输入的第一行包含一个整数 $t$ ($1 \le t \le 300,000$)，代表测试用例的数量。之后是 $t$ 个测试用例。每个测试用例包含一行，内含一个整数 $n$ ($1 \le n \le 300,000$)。

对于每个测试用例，输出一个整数，代表堆叠 $n$ 个盒子的不同方式数量，结果对 $998,244,353$ 取模。

**样例解释 #1** 第二个测试用例的 $n$ 值为 $6$，其 $12$ 种方式已在题目描述中说明。