Let be a function that calculates the digit product of in base without leading zeros. For instance:
You are given three positive integers and . Determine how many integers exist in the range whose digit product equals . Formally speaking, you are required to count the number of distinct integer solutions of where and .
The first line contains , the number of test cases.
The next lines each contain three positive integers: , and , respectively.
For each test case, print the following line:
is the test case number, starting at .
is the number of integers in the interval whose digit product is equal to .
Because can be a huge number, print it modulo .
1 9 3
7 37 6
Case 1: 1
Case 2: 3
In the first test case, there is only one number in the interval .
In the second test case, there are three numbers in the interval whose digit product equals .