[Wannafly冬令营2018Day7]强壮的排列

内存限制：256 MB 时间限制：1000 ms

我们定义一个 $1...n$ 的排列 $p$ 是强壮的，当且仅当 $n$ 是奇数，且对于所有 $1\leq i\leq \frac{n-1}{2}$，有 $p[2i]>max(p[2i-1],p[2i+1])$

现在你需要计算，有几个长度为 $n$ 的排列是强壮的，由于答案可能较大，你只需要输出答案对 $998244353$ 取模后的值

第一行一个正整数 $T$，表示数据组数 $(1\leq T\leq 10^4)$

接下来 $T$ 行，每行一个奇数 $n$，表示询问的 $n$ $(1\leq n\leq 10^5)$

输出 $T$ 行，每行一个整数表示该次询问的答案

2
16
214156035

C1696 [Wannafly冬令营2018Day7]强壮的排列