正整数 $n$ が与えられます。各ターンで次の操作を行います:
- $n$ の十進表記から数字 $d$ を一様に選びます。
- $n\leftarrow n\cdot(d+1)$ として $n$ を更新します。
$n$ が $N$ を超えるまでに必要なターン数の期待値を $998244353$ で割った余りを求めてください。
入力
1 つの入力ファイルには複数のテストケースが含まれます。
入力の最初の行には、テストケースの数を表す整数 $T$ ($1\le T\le 200$) が 1 つ与えられます。
各テストケースの最初の行には、2 つの整数 $n$ と $N$ ($1\le n\le N\le 10^{18}$) が与えられます。
出力
各テストケースについて、答えを表す整数を 1 個、1 行に出力してください。
答えが常に存在することを証明できます。
入出力例
入力 1
3 1 10 1 100 1 1000
出力 1
3 4 942786340