314 Triplet Problem

問題文

正整数 $x, y, z$ に対して $f(x, y, z)$ を以下のように定義します。

• $x, y, z$ を十進表記の文字列として解釈し、この順番に結合した文字列を $s$ とする。 この $s$ を十進整数と解釈した値を $f(x, y, z)$ とする。

例えば、 $f(3, 1, 4) = 314, ~ f(998, 24, 4353) = 998244353$ です。

正整数 $N$ が与えられます。
以下の条件をすべて満たす正整数の組 $(a, b, c)$ としてあり得るものすべてについて $f(a, b, c)$ の値を求め、それらの総和を $998244353$ で割った余りを求めてください。

• $1 \leq a, b, c \leq N$
• $a + b = c$

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

制約

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 2 \times 10^9$
• 入力はすべて整数

入力

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

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

出力

$T$ 行にわたり出力し、 $k$ 行目 $(k = 1, 2, \cdots, T)$ には $k$ 番目のテストケースについての答えを出力してください。

サンプル

入力例

5
3
10
1729
998244353
2000000000

出力例

448
63030
498020532
443383476
425187490

$1$ 番目のテストケースについて、 $N = 3$ のとき条件を満たす組は $(a, b, c) = (1, 1, 2), (1, 2, 3), (2, 1, 3)$ の $3$ つです。

それぞれについて $f(a, b, c)$ を求めて総和を出すと、 $112 + 123 + 213 = 448$ となります。