E - x + y ≡ x + y Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

正整数 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 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \leq T \leq 10^4
  • 1 \leq N \leq 10^{18}
  • 2 \leq M \leq 10^9
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで \mathrm{case}_i は i 番目のテストケースを意味する。

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

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

N M

出力

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

入力例 1

4
3 2
123 456
20260530 460
123456789123456789 998244353

出力例 1

3
0
922576091
422081792

1 番目のテストケースについて、条件を満たす (x,y) は (2,1),(2,2),(2,3) の 3 個です。

Score : 450 points

Problem Statement

For positive integers a and b, define \mathrm{concat}(a, b) as the integer formed by writing a and b one after another. More formally, \mathrm{concat}(a, b) is defined as follows.

  • Let A and B be the strings formed by writing a and b in decimal, respectively. Let C be the string formed by concatenating A and B in this order. The value of C interpreted as an integer in decimal notation is \mathrm{concat}(a, b).

For example, if a = 123 and b = 45, then \mathrm{concat}(a, b) = 12345.

You are given positive integers N and M.
Find the number, modulo 998244353, of pairs (x, y) of positive integers not greater than N such that \mathrm{concat}(x, y) \equiv x + y \pmod{M}.

You are given T test cases; solve each one.

Constraints

  • 1 \leq T \leq 10^4
  • 1 \leq N \leq 10^{18}
  • 2 \leq M \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{case}_i denotes the i-th test case:

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

Each test case is given in the following format:

N M

Output

Output T lines. The i-th line should contain the answer for the i-th test case.
For each test case, output the number, modulo 998244353, of pairs (x, y) satisfying the condition.

Sample Input 1

4
3 2
123 456
20260530 460
123456789123456789 998244353

Sample Output 1

3
0
922576091
422081792

For the first test case, three pairs (x, y) satisfy the condition: (2, 1), (2, 2), (2, 3).