#2757. [SCOI2012]Blinker的仰慕者

内存限制:128 MiB 时间限制:10 Sec

题目描述

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

输入格式

输入的第一行是一个整数N,表示Blinker想知道的信息个数。
接下来的N行,每行有三个数,A,B,K。表示 Blinker想知道编号介于A和B之间的,
重要度为K的仰慕者的编号和。          

输出格式


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

样例

样例输入


			
3
1 14 4
1 30 4
10 60 5
0<=K<=10^18

样例输出


			
18
40
66
【样例解释】
第一组样例中,在 1到14之间各位数字之积等于 4的有 4和 14,故编号和为18。

数据范围与提示

【数据范围】

对于20%的数据,保证:  2<=A<=B<=1000000000,1<=N<=30

对于50%的数据,保证:2<=A<=B<=1000000000000000000,1<=N<=30

对于100%的数据,保证:  2<=A<=B<=1000000000000000000,1<=N<=5000