分数: 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).