

X NumberTime Limit: 3000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 1209 Accepted Submission(s): 468 Problem Description Teitoku loves many different kinds of numbers, and today Little W wants him to classify some positive integers into different categories. There are $11$ categories, numbered from $0$ to $10$. For each positive integer $x$, if there exists only one type of digit $d$ $(0 \leq d \leq 9)$ that occurs in $x$ with the highest frequency, then we say $x$ should be classified into category $d$, or otherwise, in case such digit doesn't exist, we say $x$ should be classified into category $10$. For example, ● $111223$ should be classified into category $1$ since digit $1$ occurs three times, and digits $2$ and $3$ occur less than three times respectively, and ● $3345544$ should be classified into category $4$ since digit $4$ occurs three times, and digits $3$ and $5$ occur less than three times respectively, and ● $112233$ should be classified into category $10$ since digits $1$, $2$ and $3$ occur twice respectively. Little W doesn't care about category $10$ and he just wants Teitoku to tell him the number of integers ranged from $l$ to $r$ that should be classified to another category $d$. However, Teitoku can hardly solve this problem, so he asks you for help. Input There are several test cases. The first line contains an integer $T$ $(1 \leq T \leq 1000)$, denoting the number of test cases. Then follow all the test cases. For each test case, the only line contains three integers $l$, $r$ and $d$ $(1 \leq l \leq r \leq 10^{18}, 0 \leq d \leq 9)$, representing a problem. Output For each test case, output in one line the number of integers ranged from $l$ to $r$ that should be classified to category $d$. Sample Input
Sample Output
Hint For the sample cases, 1 and 11 are in category 1, 100 is in category 0 and 10 is in category 10. Source  
