#216857. [GKS 2022 #A] Interesting Integers

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 and . Find the number of interesting integers between and (both inclusive).

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

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

For each test case, output one line containing Case : , where is the test case number (starting from ) and is the number of interesting integers between and (inclusive).

样例输入 1

4
1 9
91 99
451 460
501 1000

样例输出 1

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

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

In Sample Case #, there are no interesting integers between and .

In Sample Case #, there are interesting integers between and :

1. (product of its digits is , sum of its digits is ).

2. (product of its digits is , sum of its digits is ).

3. (product of its digits is , sum of its digits is ).

4. (product of its digits is , sum of its digits is ).

5. (product of its digits is , sum of its digits is ).

Limits

.

Test Set

.

Test Set

.