Digit Products | HackerRank

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 .