ストーリー

今回は $N$ が大きいみたいです。

問題文

ある対応が取れた括弧列 $T$ に対して、次の手続きを行った後の $x$ の値を $f(T)$ とします。

• はじめ、$S$ を空集合、$x=0$ として、$i=1, 2, \cdots, N$ の順に次を行う
  • $T_i=$(ならば、$S$ に $i$ を追加する
  • $T_i=$)ならば、$S$ に含まれる最大の元を $j$ として、$T$ の開区間 $(j, i)$ を取り出した文字列に連続部分文字列として含まれる()の個数を $x$ に加算する。その後、$S$ から $j$ を取り除く

例えば、$f($()(())$)=1, f($(()()())$)=3$ です。

正整数 $N$ が与えられるので、長さ $N$ の対応が取れた括弧列 $S$ として考え得るすべての文字列に対する $f(S)$ の総和を求めてください。
答えは非常に大きくなることがあるので、$998244353$ で割った余りを求めてください。

$T$ ケース与えられるので、それぞれのケースに対して答えてください。

入力

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

$case_i$ は $i$ 番目のケースを表し、次の形式で与えられます。

$N$

• $1\leq T\leq 10^5$
• 各ケースに対して$1\leq N\leq 10^6$

出力

$T$ 行出力してください。$k(1\leq k\leq T)$ 行目には、$k$ 個目のケースに対する答えを出力してください。
各ケースに対しては、$f(S)$ の総和を $998244353$ で割った余りを $r$ として、以下の形式で出力してください。

$r$

最後に改行してください。

サンプル

3
4
2
11

1
0
0