P16872 [GKS 2022 #A] Interesting Integers

如果一个整数的各位数字之积能被各位数字之和整除，则称该整数是 **有趣的**。给定两个整数 $A$ 和 $B$，求区间 $[A, B]$（包含两端）内有趣整数的个数。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 行。 每行表示一个测试用例，包含两个整数 $A$ 和 $B$。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是区间 $[A, B]$ 内有趣整数的个数。

在样例 #1 中，由于对于一位整数，其各位数字之积与和相等，因此 $1$ 到 $9$ 之间的所有整数都是有趣的。 在样例 #2 中，$91$ 到 $99$ 之间没有有趣的整数。 在样例 #3 中，$451$ 到 $460$ 之间有 $5$ 个有趣的整数： 1. $451$（各位数字之积 $4 \times 5 \times 1 = 20$，各位数字之和 $4 + 5 + 1 = 10$）。 2. $453$（积 $4 \times 5 \times 3 = 60$，和 $4 + 5 + 3 = 12$）。 3. $456$（积 $4 \times 5 \times 6 = 120$，和 $4 + 5 + 6 = 15$）。 4. $459$（积 $4 \times 5 \times 9 = 180$，和 $4 + 5 + 9 = 18$）。 5. $460$（积 $4 \times 6 \times 0 = 0$，和 $4 + 6 + 0 = 10$）。 ### 限制条件 $1 \le T \le 100$。 **测试集 1** $1 \le A \le B \le 10^5$。 **测试集 2** $1 \le A \le B \le 10^{12}$。 翻译由 DeepSeek V4 Pro 完成