Sumit, a bright student with a passion for problem-solving, recently encountered a challenging question.
The task was to count the numbers within a range, specifically between L and R, where the product of their individual digits is divisible by a positive integer P.
Sumit loves challenges and turned to you, his helpful roommate, for assistance. Can you assist Sumit in solving this problem and showcase his impressive problem-solving skills?
Input Format:
The first line contains an integer T, representing the number of test cases.
Each of the following T lines contains three integers: L, R, and P.
Output Format:
For each test case, print the number of integers that meet the condition in a separate line.
Constraints:
1≤T≤101≤L≤R≤1091≤P≤109
For testcase 1:
We have L=12, R=15, and P = 3.
So, if we check digitwise multiplication of each number in the range [12,15], then:
- 12 = 1 * 2 = 2, which is not divisible by 3.
- 13 = 1 * 3 = 3, and it is divisible by 3.
- 14 = 1 * 4 = 4, which is not divisible by 3.
- 15 = 1 * 5 = 5, which is not divisible by 3.
So, the answer is 1 only, indicating that there is only one number in the range that has a digitwise multiplication divisible by 3, and that is 13.
