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$.
SampleInput
3
1 10 1
1 11 1
1 100 0
SampleOutput
1
2
1
HintFor the sample cases, 1 and 11 are in category 1, 100 is in category 0 and 10 is in category 10.