题目描述

長さ $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$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

输入格式

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

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

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

$N$

输出格式

$T$ 行出力せよ。

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

题目大意

对于一个长度为 $n$ 的正整数序列 $X=(X_1,X_2,\cdots,X_n)$，定义 $f(X)$ 为：

• 对于所有节点数量为 $n$，且点 $i$ 的度数恰好为 $X_i$ 的树，其直径的最大值。如不存在，则值为 $0$。

你需要对于所有长度为 $n$ 的正整数序列 $X$ 计算 $f(X)$ 的和，可以证明其为有限值。答案对 $998244353$ 取模。

$T$ 组数据。$1\le T\le2\times10^5$，$2\le n\le10^6$。

—— by Register_int

10
2
3
5
8
13
21
34
55
89
144

1
6
110
8052
9758476
421903645
377386885
881422708
120024839
351256142

提示

制約

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

Sample Explanation 1

$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$ です。