题目描述

在 Whacker Cup 于 Meta 园区举行期间，访客需要把随身物品存放在储物柜中。这些储物柜通常是给尚未分配固定工位的培训生使用的。

储物柜需要设置密码，密码是正整数。组织者原本计划直接从闭区间 $[L,R]$ 中分配密码，但他们担心这些密码在密码学意义上的强度。

对于任意整数 $K>1$，如果一个密码 $X$ 的十进制表示中，存在至少一个连续子串，使得该子串的数字和能被 $K$ 整除，则称 $X$ 在 Meta 的特殊加密方案中是 $K$-weak 的。

例如，$29231$ 是 $7$-weak 的，因为它包含子串 $923$，其数字和为 $14$，可以被 $7$ 整除；但 $512$ 不是 $7$-weak 的。

请计算区间 $[L,R]$ 中有多少个不同的 $K$-weak 密码。由于答案可能很大，请输出其对 $998244353$ 取模后的结果。

数据范围

• $1 \le T \le 80$
• $1 \le L \le R \le 10^{2025}$
• $2 \le K \le 25$

输入格式

输入第一行包含一个整数 $T$，表示测试用例数。

每个测试用例占一行，包含三个空格分隔的整数 $L,R,K$。

注意：$L$ 和 $R$ 可能非常大，应按大整数或字符串处理。

输出格式

对于第 $i$ 个测试用例，输出：

Case #i: x

其中 $x$ 表示区间 $[L,R]$ 中 $K$-weak 密码的数量，对 $998244353$ 取模。

样例输入

4
1 3 2
129 135 5
98 3669 11
12345678 87654321 20

样例输出

Case #1: 1
Case #2: 4
Case #3: 2025
Case #4: 66132213

样例解释

第一个样例中，需要统计 $[1,3]$ 内的 $2$-weak 密码。区间中唯一的 $K$-weak 密码是 $2$，它唯一的子串 2 的数字和为 $2$，能被 $2$ 整除。因此答案为 $1$。

第二个样例中，需要统计 $[129,135]$ 内的 $5$-weak 密码：

• $129$ 的所有子串为 $[1,2,9,12,29,129]$，对应数字和为 $[1,2,9,3,11,12]$。这些数字和都不能被 $5$ 整除，所以 $129$ 不是 $5$-weak；
• $130$ 包含子串 0，其数字和为 $0$，能被 $5$ 整除，所以它是 $5$-weak；
• $131$ 包含子串 131，其数字和为 $5$，能被 $5$ 整除，所以它是 $5$-weak；
• $132$ 包含子串 32，其数字和为 $5$，所以它是 $5$-weak；
• $133$ 和 $134$ 不是 $5$-weak；
• $135$ 包含子串 5，所以它是 $5$-weak。

因此最终答案为 $4$。