Numbers with product K

Ninja Ankush likes to brag that he is the Ultimate Ninja among his peers. Therefore his fellow Ninja Nikhil gave him a riddle to check if Ankush is really the Ultimate Ninja. Nikhil gave Ankush a range and a number ‘K’, and asked how many numbers exist in the range such that the product of the digits of the number is equal to ‘K’. Help Ninja Ankush to prove to Ninja Nikhil that he, in fact, is the Ultimate Ninja.

More Formally, Given three positive integers ‘L’, ‘R’ and ‘K’, the task is to count the numbers in the range ‘L’ and ‘R’ inclusive, whose product of digits is equal to ‘K’.

For example

Given:
‘L’ = 1, ‘R’ = 23, ‘K’ = 6.

The answer will be 3 since there are three numbers between 1 and 23 whose product of digits is 6, and those are 6, 16, and 23.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

Next, ‘T’ lines consist of three space-separated integers, ‘L’, ‘R’, ‘K’.

Output Format :

For each test case, return the count of numbers between ‘L’ and ‘R’ whose product of digits is ‘K’.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1 <= ‘T’ <= 10
1 <= ‘L’ <= 10 ^ 8
‘L’ <= ‘R’ <= 10 ^ 8
1 <= ‘K’ <= 10 ^ 4

Time Limit: 1sec.