AT_abc460_e.x + y ≡ x + y

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.

对于正整数 $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$，
求满足 $1 \le x, y \le N$ 且 $\mathrm{concat}(x, y) \equiv x + y \pmod{M}$ 的正整数对 $(x, y)$ 的个数（对 $998244353$ 取模）。

共给出 $T$ 组测试用例，请对每组分别求解。

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$

输入从标准输入给出，格式如下，其中 $\mathrm{case}_i$ 表示第 $i$ 个测试用例：

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

每个测试用例的格式如下：

$N$ $M$

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.

输出 $T$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案。
对于每个测试用例，输出满足条件的数对 $(x, y)$ 的个数对 $998244353$ 取模的结果。

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

Constraints

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

样例 1 解释：
对于第一个测试用例，共有三对 $(x, y)$ 满足条件：$(2, 1), (2, 2), (2, 3)$。

限制条件

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