問題文

以下の条件を満たす木 $S$ を Slime Tree と定義します。ただし、$|X|$ はグラフ $X$ の頂点数を表します。

• 頂点数が $2$ 冪である。
• $|S|>1$ ならばある部分木 $P$ が存在し、以下の条件を満たす。
  • $2 |P| = |S|$
  • $P$ はパスグラフである。すなわち、ある $2$ 頂点 $u,v$ が存在し ($u=v$ でもよい)、$P$ の全ての頂点は頂点 $u,v$ を結ぶ単純パス上にある。
  • $S$ から $P$ に含まれる頂点を除いた頂点集合からなる誘導部分グラフは連結で、かつ Slime Tree である。

$T$ 個のテストケースで非負整数 $N$ が与えられるので、それぞれに対して $2^N$ 頂点のラベルなし Slime Tree の個数を $998244353$ で割った余りを求めてください。

入出力が多いので、高速な方法を用いて入出力を行うことを推奨します。

制約

• $1 \le T \le 10^6$
• $0 \le N \le 10^6$

入力

$T$
$N_1$
$N_2$
$\vdots$
$N_T$

出力

各テストケースに対して $1$ 行ずつ答えを出力し、最後に改行してください。

サンプル

5
0
1
2
3
4

1
1
1
3
58