問題文

次の条件を満たす文字列 $S$ を「ほぼ回文」と呼びます。

• $S$ は a から z までの英小文字からなる文字列である。
• $S$ は回文ではない。
• $S$ から $i$ 文字目を取り除いたものが回文になるような $i\ (1 \leq i \leq |S|)$ が存在する。

例えば、 $S = $ nyaan とすると、$S$ は回文ではないですが、2文字目の y を取り除いた naan は回文なので $S$ は「ほぼ回文」です。

$N$ が与えられるので、長さ $N$ の「ほぼ回文」の個数を $998244353$ で割ったあまりを求めてください。

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

制約

• 入力は全て整数である。
• $1 \leq T \leq 10^5$
• $1 \leq N \leq 10^6$

入力

$T$
$\mathrm{case}1$
$\vdots$
$\mathrm{case}T$

$N$

出力

$T$ 行出力して最後に改行してください。
$i$ 行目には $i$ 番目のテストケースに対する答えを出力してください。

サンプル

5
1
2
3
100
133333

0
650
1300
81960607
708231776