← 返回题目列表

AtCoder · abc460_e

E. x 加 y 同余于 x 加 y

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

对于正整数 a 和 b,定义 \mathrm{concat}(a, b) 作为通过写入形成的整数 a 和 b 一个又一个。更正式地说, \mathrm{concat}(a, b) 定义如下。

  • 让 A 和 B 是通过书写形成的字符串 分别为十进制的 a 和 b 。让 C 是连接形成的字符串 A 和 B 按此顺序。的价值 C 解释为十进制整数是 \mathrm{concat}(a, b).

例如,如果 a = 123 和 b = 45,那么 \mathrm{concat}(a, b) = 12345.

给你正整数 N 和 M.
求模数 998244353,成对 (x, y) 的正整数不大于 N 这样 \mathrm{concat}(x, y) \equiv x + y \pmod{M}.

你被给予 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- 第一个测试用例。
对于每个测试用例,输出数字,模数 998244353,成对 (x, y) 满足条件。


示例输入 1

4
3 2
123 456
20260530 460
123456789123456789 998244353

示例输出 1

3
0
922576091
422081792

对于第一个测试用例,三对 (x, y) 满足条件: (2, 1), (2, 2), (2, 3).