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 .
Input Format
The first line contains , the number of test cases.
The next lines each contain three positive integers: , and , respectively.
Constraints
Output Format
For each test case, print the following line:
Case
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 .
Sample Input
2
1 9 3
7 37 6
Sample Output
Case 1: 1
Case 2: 3
Explanation
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 .