問題文

正整数 $n$ が良い数であるとは、 $n$ が以下の条件を満たすことと定義します。

• $n$ を十進数と解釈したときの $10^i$ の位の値を $n_i$ としたとき、 $n_{i+2} > n_{i+1} + n_i$ を満たす非負整数 $i$ が存在する。

また、正整数 $n$ に対して $f(n)$ を、$n$ 以上の良い数の最小値と定義します。

正整数 $N$ が与えられます。 $f(1) + f(2) + \cdots + f(N)$ の値を $998244353$ で割った余りを求めてください。

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

制約

• 入力される値はすべて整数
• $1 \leq T \leq 200$
• $1 \leq N \leq 10^{18}$

入力

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

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

各テストケースは以下の形式で与えられる。

$N$

出力

各テストケースについての答えを順に改行区切りで出力せよ。

サンプル

4
10
668
169231
1000000000000000000

1000
245820
346334860
992299114