该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小 $\verb!B!$ 得到了一个迷宫，其大小为 $(n+1) \times (n+1)$，他发现有 $C^{2n}_{n}$ 条最短的路径可以从迷宫的 $(0, 0)$ 走到 $(n, n)$。

小 $\verb!B!$ 想知道如果在不穿过迷宫对角线（可触碰对角线）的情况下有多少条路径可以使得从迷宫的 $(0, 0)$ 走到 $(n, n)$，请你帮他求出答案对 $998244353$ 后的结果。

输入格式

第一行一个整数 $T$，表示输入数据的组数。

接下来 $T$ 行每行一个整数 $n$，表示迷宫的大小。

输出格式

输出共 $T$ 行，对于每一个给定的 $n$，输出一个整数表示答案对 $998244353$ 后的结果。

样例输入输出

5
16
3
14
20
11

70715340
10
5348880
151064251
117572

7
3
17
6
9
1
11
4

10
259289580
264
9724
2
117572
28

说明/提示

【样例解释 #2 ##7】

当 $n = 4$ 时，部分迷宫如下：

其中 $(0, 0)$ 为起点，$(4, 4)$ 为终点，其中箭头表示可以从当前点走到下一个点。

【数据范围】

对于 $40\%$ 的数据，满足 $1 \le T \le 50$, $1 \le n \le 100$；

对于 $100\%$ 的数据，满足 $1 \le T \le 100$, $1 \le n \le 10^3$。