問題文

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

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

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

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

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

制約

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

入力

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

$N$

出力

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

サンプル

5
1
2
3
100
133333

0
650
1300
81960607
708231776