P5842 [SCOI2012] Blinker’s Admirers

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$.

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 $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$.

## 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