还记得问题 B 中的 Barney 吗？他的姐姐 Cecilia 经常看着他玩积木。她也经常加入 Barney 的游戏，并且大部分时间都赢了，这让 Barney 的自信心每天都受到打击。

有一天，Cecilia 注意到 Barney 正在努力用他的 $n$ 个积木搭建一个对称的楼梯。她立刻告诉他，她不仅能搭建出一个对称的楼梯，甚至还能算出由 $n$ 个积木组成的对称楼梯的数量！你能做到吗？

回想一下，对称楼梯由一个或多个积木塔组成，塔的高度从左到右非递增，并且关于直线 $x = y$ 对称（其中 $x$ 轴水平向右， $y$ 轴垂直向上）。有关更详细的解释，请参考问题 B 的描述。

不同对称楼梯的数量可能非常大，因此你需要计算其对 $998\,244\,353$ 取模的结果。

输入格式

输入包含多个测试用例。

第一行包含一个整数 $t$ —— 测试用例的数量 ($1 \le t \le 10^4$)。接下来的 $t$ 行，每行包含一个整数 $n_i$ —— 第 $i$ 个测试用例中积木的数量 ($1 \le n_i \le 2 \cdot 10^5$)。

输出格式

对于每个测试用例，输出一行，包含一个整数 —— 由恰好 $n_i$ 个积木组成的对称楼梯的数量，对 $998\,244\,353$ 取模。

样例

样例输入 1

4
3
5
17
25

样例输出 1

1
1
5
12

说明

下图中展示了所有 $n = 17$ 个积木组成的对称楼梯：