Count Numbers Containing Given Digit K Times

Ninja is in college and he is learning about numbers and counting he got an assignment in that and that task is hard for Ninja so he wants help from you. He has been provided with two numbers ‘L’ and ‘R’ which represent the range, Both numbers are inclusive. He has been provided with two more numbers which are ‘D’ and ‘K’ and now he has to do find the following :

What is the count of numbers in the range [L, R] in which each number has digit ‘D’ exactly ‘K’ times?

Example:

Input: ‘L’ = 1, ‘R’ = 12, ‘D’ = 2, ‘K’ = 1 

Output: 2

As in the range, numbers are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, and 2, 12 are the numbers where the digit ‘2’ comes exactly once.

Input Format :

The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains ‘L’ and ‘R’ the left and right boundaries of the range.
The second line contains ‘D’ the digit for which we have to check.
The third line contains 'K' the count of the digit 'D'.

Output format :

For each test case, print the count of numbers satisfying the given criteria.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= L <= R <= 10^9
0 <= D <= 9
0 <= K <= 18

Time Limit: 1 sec

Sample Input 1 :

2
1 5
3
1
3 10
4
1

Sample Output 1 :

1
1

Explanation Of Sample Input 1 :

For the first case :
There is only one number 3 in the range [1, 5] is there whose digit count of 3 is 1 so the answer is 1.

For the second case :
There is only one number 4 in the range [3, 10] is there whose digit count of 4 is 1 so the answer is 1.

Sample Input 2 :

2
10 15
3 
1
1 20
5
0

Sample Output 2 :

1
18