AT_abc460_e [ABC460E] x + y ≡ x + y

正整数 $ a,b $ に対して、 $ a $ と $ b $ を繋げて書いた時に出来る整数を $ \mathrm{concat}(a, b) $ と呼びます。厳密に述べると、 $ \mathrm{concat}(a, b) $ を次のように定義します。 - $ a, b $ を $ 10 $ 進表記して出来る文字列を $ A, B $ とする。 $ A, B $ をこの順に結合して出来る文字列を $ C $ とする。 $ C $ を $ 10 $ 進表記された整数とみなした時の値を $ \mathrm{concat}(a, b) $ とする。 例えば $ a = 123, b = 45 $ の時 $ \mathrm{concat}(a, b)=12345 $ です。 正整数 $ N, M $ が与えられます。 $ N $ 以下の正整数の組 $ (x,y) $ であって $ \mathrm{concat}(x, y) \equiv x + y \pmod{M} $ であるものの個数を $ 998244353 $ で割った余りを求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。ここで $ \mathrm{case}_i $ は $ i $ 番目のテストケースを意味する。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ M $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースの答えを出力せよ。 各テストケースでは、条件を満たす $ (x,y) $ の個数を $ 998244353 $ で割った余りを出力せよ。

### Sample Explanation 1 1 番目のテストケースについて、条件を満たす $ (x,y) $ は $ (2,1),(2,2),(2,3) $ の $ 3 $ 個です。 ### Constraints - $ 1 \leq T \leq 10^4 $ - $ 1 \leq N \leq 10^{18} $ - $ 2 \leq M \leq 10^9 $ - 入力される値は全て整数