题目描述

Let us call an integer interesting if the product of its digits is divisible by the sum of its digits. You are given two integers $A$ and $B$. Find the number of interesting integers between $A$ and $B$ (both inclusive).

输入格式

The first line of the input gives the number of test cases, $T$. $T$ lines follow.

Each line represents a test case and contains two integers: $A$ and $B$.

输出格式

For each test case, output one line containing Case $\#x$: $y$, where $x$ is the test case number (starting from $1$) and $y$ is the number of interesting integers between $A$ and $B$ (inclusive).

4
1 9
91 99
451 460
501 1000

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

提示

In Sample Case #$1$, since the product and the sum of digits are the same for single-digit integers, all integers between $1$ and $9$ are interesting.

In Sample Case #$2$, there are no interesting integers between $91$ and $99$.

In Sample Case #$3$, there are $5$ interesting integers between $451$ and $460$:

1. $451$ (product of its digits is $4 \times 5 \times 1 = 20$, sum of its digits is $4 + 5 + 1 = 10$).

2. $453$ (product of its digits is $4 \times 5 \times 3 = 60$, sum of its digits is $4 + 5 + 3 = 12$).

3. $456$ (product of its digits is $4 \times 5 \times 6 = 120$, sum of its digits is $4 + 5 + = 15$).

4. $459$ (product of its digits is $4 \times 5 \times 9 = 180$, sum of its digits is $4 + 5 + 9 = 18$).

5. $460$ (product of its digits is $4 \times 6 \times 0 = 0$, sum of its digits is $4 + 6 + 0 = 10$).

Limits

$1 \le T \le 100$.

Test Set $1$

$1 \le A \le B \le 10^5$.

Test Set $2$

$1 \le A \le B \le 10^{12}$.