- Prepare
- Mathematics
- Combinatorics
- Digit Products

# Digit Products

# Digit Products

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 .