Description

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

Input

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

Output

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

Sample Input

Sample Output

Hint

【数据范围】

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

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

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

Source