問題文

非負整数 $n, i$ に対し $n_i$ を、$n$ を $10$ 進数表記したときの $10^i$ の位の値と定義します。

定義1（monotonic）

正整数 $n$ が monotonic であるとは、 $i < j$ ならば $n_i \ge n_j$ であることと定義します。特に、$\color{red}1$ 桁の正整数は monotonic です。

例えば、$123, 2233355555, 1$ は monotonic ですが、$321, 998244353$ は monotonic ではありません。

定義2（forever-monotonic）

正整数 $n$ が forever-monotonic であるとは、 任意の非負整数 $k$ について以下の条件が成り立つことと定義します。

• $n$ を 「$n$ を $10$ 進数表記したときの各桁の和」に置き換える操作を $k$ 回繰り返し行う。操作後の $n$ は monotonic である。

非負整数 $N$ が与えられます。$10^{N}$ 以上の forever-monotonic な整数のうち最小のものを求めてください。
ただし、答えが非常に大きくなる場合があるため、答えを $998244353$ で割った余りを出力してください。

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

制約

• $1 \leq T \leq 10^5$
• $0 \leq N \leq 10^{14}$
• $T, N$ は整数

入力

入力は以下の形式で標準入力から与えられます。ここで、$\mathrm{case}_i ~ (i = 1, 2, \cdots, T)$ は $i$ 番目のテストケースです。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

各テストケースは以下の形式で標準入力から与えられます。

$N$

出力

$T$ 行出力してください。$i$ 行目には、$i$ 番目のテストケースについての答えを $998244353$ で割った余りを出力してください。

サンプル

6
0
2
9
1024
123456789
99999999999999

1
111
112866759
614307571
646823187
411251028