We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Mathematics
  3. Combinatorics
  4. Digit Products

Digit Products

Problem
Submissions
Leaderboard
Discussions
Editorial

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 .

Author

sgtlaugh

Difficulty

Medium

Max Score

60

Submitted By

216

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy