Zack 的 Zergonomics Zegree 课程告诉他，在商店中展示商品的最优方式是将它们堆叠成锯齿状。

Zack 需要在店面排成一排展示 $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 所示。

图 M.1：$n = 6$ 时所有 12 种可能的方式。

求 Zack 堆叠 $n$ 个盒子的不同方式数量，结果对 998 244 353 取模。

当且仅当堆叠的数量相同，且相同位置的堆中盒子数量也相同时，两种方式被视为相同。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 300\,000$)，表示测试用例的数量。接下来是 $t$ 个测试用例。每个测试用例由一行组成，包含一个整数 $n$ ($1 \le n \le 300\,000$)。

输出格式

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

样例

输入 1

4
5
6
7
890

输出 1

7
12
19
502674609

说明

第二个测试用例中 $n$ 的值为 6，题目描述中展示了这 12 种方式。