Problem Description

Blinker has many admirers, and he gives each admirer a positive integer ID. These IDs also hide a special meaning: the product of the digits of an ID represents how important this admirer is to Blinker. Now Blinker wants to know the sum of all admirer IDs between two values $A$ and $B$, whose importance equals a fixed value $K$.

Input Format

The first line contains an integer $N$, which represents the number of queries Blinker wants to ask.

The next $N$ lines each contain three numbers $A$, $B$, and $K$, meaning Blinker wants the sum of all admirer IDs between $A$ and $B$ whose importance is $K$.

Output Format

Output $N$ lines. For each query, output the sum of all admirer IDs between $A$ and $B$ whose importance is $K$. Since the result may be very large, take it modulo $20120427$.

3
1 14 4
1 30 4
10 60 5

18
40
66

Hint

Constraints

• For $20\%$ of the testdata: $2 \le A \le B \le 10^9$, $1 \le N \le 30$.
• For $50\%$ of the testdata: $2 \le A \le B \le 10^{18}$, $1 \le N \le 30$.
• For $100\%$ of the testdata: $2 \le A \le B \le 10^{18}$, $1 \le N \le 5000$.

Translated by ChatGPT 5