配点 : $500$ 点

問題文

長さ $N$ の正整数列 $X=(X_1,X_2\ldots,X_N)$ に対して、$f(X)$ を以下のように定めます。

• $N$ 頂点の木であって、$i\ (1 \leq i \leq N)$ 番目の頂点の次数が $X_i$ であるようなものを良い木と呼ぶ。 良い木が存在するならば、$f(X)$ は良い木の直径の最大値。良い木が存在しないならば、$f(X)=0$。

ただし、木の $2$ 頂点の間の距離は一方から他方へ移動するときに用いる辺の本数の最小値であり、 木の直径は任意の $2$ 頂点の間の距離の最大値として定められます。

長さ $N$ の正整数列 $X$ としてあり得るもの全てに対する $f(X)$ の総和を $998244353$ で割った余りを求めてください。 なお、$f(X)$ の総和は有限値になることが証明できます。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• $1\leq T \leq 2\times 10^5$
• $2 \leq N \leq 10^6$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで、$\mathrm{test}_i$ は $i$ 番目のテストケースを意味する。

$T$

$\mathrm{test}_1$

$\mathrm{test}_2$

$\vdots$

$\mathrm{test}_T$

各テストケースは以下の形式で与えられる。

$N$

出力

$T$ 行出力せよ。

$i\ (1\leq i \leq T)$ 行目には、$i$ 番目のテストケースに対する答えを出力せよ。

10
2
3
5
8
13
21
34
55
89
144

1
6
110
8052
9758476
421903645
377386885
881422708
120024839
351256142

$N=3$ の場合について、

例えば、

• $X=(1,1,1)$ のとき、次数が $1,1,1$ となる $3$ 頂点の木は存在しないため、$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$ です。