题目描述

对于正整数 $a$ 和 $b$，定义 $\mathrm{concat}(a, b)$ 为将 $a$ 和 $b$ 前后拼接所形成的整数。

更准确地说，设 $A$ 和 $B$ 分别为 $a$ 和 $b$ 的十进制表示字符串，$C$ 为 $A$ 后接 $B$ 形成的字符串，则 $\mathrm{concat}(a, b)$ 即 $C$ 作为十进制整数的值。

例如，$a = 123$ 且 $b = 45$ 时，$\mathrm{concat}(a, b) = 12345$。

给定两个正整数 $N$ 和 $M$。请找出满足以下条件的正整数对 $(x, y)$ 的数量（结果对 $998244353$ 取模）：

• $x$ 和 $y$ 均不超过 $N$；
• 满足同余式 $\mathrm{concat}(x, y) \equiv x + y \pmod{M}$。

给定 $T$ 个测试用例，请分别求解。

输入格式

T
case_1
case_2
...
case_T

每个测试用例按以下格式给出：

N M

输出格式

输出 $T$ 行，第 $i$ 行表示第 $i$ 个测试用例的答案对 $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)$。

约束条件

• $1 \le T \le 10^4$
• $1 \le N \le 10^{18}$
• $2 \le M \le 10^9$
• 所有输入值均为整数