Migrated from Lutece 3233 简单的数列题

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

注：本题不计一血 波波王得到了一个数列，它满足这样的递推关系：

$$a_n=\sum_{i=0}^{n-1}a_ia_{n-1-i},n\geq 2\\ a_0=a_1=1 $$

波波王希望给你 $n$ 个值 $m_i$，对于每个 $m_i$，你可以求出 $a_{m_i}$ 的值。 由于这个值可能会很大，因此你需要对 $998244353$ 取模。

Input

第一行一个数 $n$，表示 $m$ 的数量。 接下来 $n$ 行，第 $i$ 行一个整数，表示 $m_i$.

Output

$n$ 行，每行一个数，第 $i$ 行表示 $a_{m_i}$ 对 $998244353$ 取模的结果。

Samples

2
1
3

1
5

Constraints

$1\leq n\leq 10^6,1\leq m\leq 10^6$

Resources

2024 UESTC ICPC Training for Math