24842번 - 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 $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).

제한

• 1ドル≤T≤100$.

Test Set 1 (11점)

• 1ドル≤A≤B≤10^5$.

Test Set 2 (24점)

• 1ドル≤A≤B≤10^{12}$.

힌트

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 five interesting integers between 451ドル$ and 460ドル$:

1. 451ドル$ (product of its digits is 4ドル×5×1=20,ドル sum of its digits is 4ドル+5+1=10$).
2. 453ドル$ (product of its digits is 4ドル×5×3=60,ドル sum of its digits is 4ドル+5+3=12$).
3. 456ドル$ (product of its digits is 4ドル×5×6=120,ドル sum of its digits is 4ドル+5+6=15$).
4. 459ドル$ (product of its digits is 4ドル×5×9=180,ドル sum of its digits is 4ドル+5+9=18$).
5. 460ドル$ (product of its digits is 4ドル×6×0=0,ドル sum of its digits is 4ドル+6+0=10$).