X Number

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

3
1 10 1
1 11 1
1 100 0

Sample Output

1
2
1

Hint

For the sample cases, 1 and 11 are in category 1, 100 is in category 0 and 10 is in category 10.

Source

2020 Multi-University Training Contest 3