题目描述

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

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 行。

每行表示一个测试用例，包含两个整数 $A$ 和 $B$。

输出格式

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

4
1 9
91 99
451 460
501 1000

Case #1: 9
Case #2: 0
Case #3: 5
Case #4: 176

提示

在样例 #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 完成