[SCOI2012] Blinker 的仰慕者

题目描述

Blinker 有非常多的仰慕者，他给每个仰慕者一个正整数编号。而且这些编号还隐藏着特殊的意义，即编号的各位数字之积表示这名仰慕者对 Blinker 的重要度。 现在 Blinker 想知道编号介于某两个值 $A$,$B$ 之间，且重要度为某个定值 $K$ 的仰慕者编号和。

输入格式

输入的第一行是一个整数 $N$，表示 Blinker 想知道的信息个数。

接下来的 $N$ 行，每行有三个数，$A$,$B$,$K$。表示 Blinker想知道编号介于 $A$ 和 $B$ 之间的，重要度为 $K$ 的仰慕者的编号和。

输出格式

输出 $N$ 行，每行输出介于 $A$ 和 $B$ 之间，重要度为 $K$ 的仰慕者编号和。结果可能很大请对 $20120427$ 取模。

样例 #1

样例输入 #1

3
1 14 4
1 30 4
10 60 5

样例输出 #1

18
40
66

提示

• 对于 $20\%$ 的数据，保证： $2 \le A \le B \le 10^9$，$1 \le N \le 30$；
• 对于 $50\%$ 的数据，保证：$2 \le A \le B \le 10^{18}$，$1\le N \le 30$；
• 对于 $100\%$ 的数据，保证： $2 \le A \le B \le 10^{18}$，$1 \le N \le 5000$。