123456789

問題文

文字列 $S = \text{"123456789"}$ とします。
文字列 $T$ を、$S$ を $10^{100}$ 回連結して得られる文字列とします。
より厳密には、任意の正の整数 $j$ に対し、$T$ の $j$ 文字目 $T_j$ は $((j-1) \pmod 9) + 1$ となります。

$Q$ 個のクエリが与えられますので、順に処理してください。\

・$i$ 番目（$1 \le i \le Q$）のクエリでは3つの整数 $l_i, r_i, M_i$ が与えられます。
・$T$ の $l_i$ 文字目から $r_i$ 文字目までを順に連結した長さ $r_i - l_i + 1$ の連続部分文字列を $T[l_i, r_i]$ とします。
・この $T[l_i, r_i]$ を、$M_i$ 個の空でない連続する部分文字列 $A_1, A_2, \dots, A_{M_i}$ に分割することを考えます（すなわち、 $A_1, A_2, \dots, A_{M_i}$ をこの順番に連結すると、$T[l_i,r_i]$ に一致するように $A_1, A_2, \dots, A_{M_i}$ を定める。)
・各 $A_k$ を 10 進法表記の整数とみなし、その値を $v(A_k)$ とします。この分割におけるスコアを $\min_{1 \le k \le M_i} v(A_k)$ と定義します。
・すべての可能な分割におけるスコアの最大値 $X_i$ を求めてください。ただし、値が非常に大きくなる可能性があるため、$X_i \pmod{998244353}$ を出力してください。

---

制約

• $1 \le Q \le 2 \times 10^5$
• $1 \le l_i \le r_i \le 10^{18}$
• $1 \le M_i \le r_i - l_i + 1$
• 入力はすべて整数である

---

入力

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

---

出力

$Q$ 行出力せよ。 $i$ 行目（$1 \le i \le Q$）には、$i$ 番目のクエリにおけるスコアの最大値 $X_i$ を 998244353 で割った余りを出力せよ。

---

入力例 1

出力例 1

1番目のクエリでは、$T[1, 3]$ は文字列 "123" となります。これを $M_1 = 2$ 個の部分文字列に分割する方法は ("1", "23") と ("12", "3") の2通り存在します。それぞれのスコア（分割された値の最小値）は $\min(1, 23) = 1$ と $\min(12, 3) = 3$ になります。このうち最大となるのは 3 であるため、3 を出力します。
3番目のクエリでは、$T[1, 5]$ は文字列 "12345" であり、これを $M_3 = 1$ 個に分割する（すなわち分割を行わない）ため、文字列全体をそのまま整数とみなした 12345 がスコアとなり、最大値も 12345 となります。

---

入力例 2

出力例 2

$998244353$ で割ったあまりを出力することに注意してください。