配点：$600$ 点

問題文

正四面体の各面がそれぞれ赤、青、黄、緑に塗られています。 riano君は初め赤に塗られている面にいて、今いる面以外のいずれかの面に等確率で移動することを $N$ 回繰り返します。 この際、riano君の移動前後の面の色が入れ替わります。

$N$ 回の移動の後の正四面体の色の配置が、元の配置と同じになっている確率はいくらでしょうか。 ただし、正四面体は空間内に固定されており、一切動かさずに同じ色の配置である時のみ、元の配置と同じとみなします。

ここでは $T$ 個の$N_i$ $(1\leq i\leq T)$ が与えられますので、それぞれの $N_i$ に対して答えを求めてください。 また、この確率は有理数であることが証明できますので、mod $998244353$ で答えてください。 厳密には、答えを既約分数で $P/Q$ と表したとき、$P=Q\times R$ $($mod $998244353)$ となる $0$ 以上 $998244353$ 未満の整数 $R$ を答えてください。

制約

• $1 \leq T \leq 10^4$
• $0 \leq N_i \leq 10^{12}$ $(1\leq i\leq T)$
• 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられます。

出力

$T$ 行に渡って出力し、$i$ 行目には $N_i$ に対する上述の $R$ の値を出力してください。

サンプル

4
0
1
2
12345678910

1
0
332748118
977313685

移動回数が $0$ 回の場合、明らかに元の色の配置のままです。 移動回数が $1$ 回の場合、この移動によって何らかの色が入れ替わるため元通りであることはありえません。 移動回数が $2$ 回の場合、例えば図のように青の面に移動し、戻ってくるような経路で移動すると色が元通りになります。 この時、青に限らずどの面への往復でもよいことから条件を満たす移動経路は $3$ 通りです。 また、可能な移動経路は全部で $9$ 通りあるため、求める確率は $1/3$ となります。

また、$4$ 番目のテストケースのように、入力が大きな値になることがありますので注意してください。