Chef and special numbers

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef's team is going to participate in the legendary math battles. This time the main task of the competition is to calculate number of Kspecial numbers in the range [L, R] (i.e. L, L + 1, L + 2, ..., R).
A number X is said to be Kspecial if there exist K or more different digits, such that X is divisible by those digits and those digits are present in the decimal representation of the number. For example, number 48 is both 1 and 2 special, as it is divisible by digits 4 and 8. Note that no positive integer is divisible by number 0.
Chef asked you to help him with this task. There will be Q questions of forms L, R, K. For each of these questions, you have to tell How many Kspecial numbers are the range [L, R] ?".
Input
First line of the input contains an integer Q that denotes number of questions Chef was asked.
In the next Q lines follow the questions, ith of the line will denote the ith question represented by three space separated integer L, R, K respectively.
Output
For each question, output an integer in a separate line containing the answer of the question.
Constraints and Subtasks

Subtask 1 : [10 points]
 1 ≤ Q ≤ 3
 1 ≤ L ≤ R ≤ 10^{6}
 0 ≤ K ≤ 9
Subtask 2 : [20 points]
 1 ≤ Q ≤ 3
 1 ≤ L ≤ R ≤ 10^{9}
 0 ≤ K ≤ 9
Subtask 3 : [70 points]
 1 ≤ Q ≤ 3
 1 ≤ L ≤ R ≤ 10^{18}
 0 ≤ K ≤ 9
Example
Input: 3 48 48 1 48 48 2 5 15 1 Output: 1 1 11
Explanation
Example case 1 and 2. 48 is both 1 and 2 special as explained in the problem statement. Hence answer is 1.
Author:  omelyanenko 
Tester:  mugurelionut 
Editorial  http://discuss.codechef.com/problems/WORKCHEF 
Tags  digitdp, july16, maths, medium, omelyanenko 
Date Added:  9052016 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 