题目描述

对于一个由正整数组成的长度为$N$的序列$X=(X_1,X_2,\ldots,X_N)$，我们定义$f(X)$如下：

• 当且仅当第$i$个$(1 \leq i \leq N)$顶点的度数为$X_i$时，拥有$N$个顶点的树被称为好的树。如果存在一棵好的树，$f(X)$就是一棵好的树的最大直径；如果不存在，$f(X)=0$。

这里，两个顶点之间的距离是从一个顶点到另一个顶点所需遍历的最小边数，而一棵树的直径是两个顶点之间的最大距离。

计算长度为$N$的所有可能序列$X$的$f(X)$之和对$998244353$取模的结果。我们可以证明$f(X)$的和是一个有限值。

给定$T$个测试用例，求每个测试用例的答案。

约束条件

• $1 \leq T \leq 2 \times 10^5$
• $2 \leq N \leq 10^6$
• 输入中的所有值都是整数。

输入

从标准输入读入输入数据。输入格式如下，其中$\text{test}_i$表示第$i$个测试用例：

$T$ $\text{test}_1$ $\text{test}_2$ $\vdots$ $\text{test}_T$

每个测试用例的格式如下：

$N$

输出

输出结果到标准输出。输出格式如下：

输出$T$行。

第$i$行（$1 \leq i \leq T$）包含第$i$个测试用例的答案。

示例输入1

10
2
3
5
8
13
21
34
55
89
144

示例输出1

1
6
110
8052
9758476
421903645
377386885
881422708
120024839
351256142

当$N=3$时：

例如，

• 当$X=(1,1,1)$时，不存在顶点度数为$1,1,1$的三个顶点的树，因此$f(X)=0$。
• 当$X=(2,1,1)$时，唯一可能的树如下所示。这棵树的直径为$2$，因此$f(X)=2$。

对于$X=(2,1,1),(1,2,1),(1,1,2)$，我们有$f(X)=2$，对于其他$X$，我们有$f(X)=0$。因此，答案为$6$。