2706: 数的计数
内存限制：64 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：7
解决：7
题目描述
小A终于找到了一份工作！工作的内容是统计[L,R]区间的K超级数的数目。X是K超级数，当且仅当X各位数字之和的K倍能被X整除（整除的定义大家都懂吧）。小A的Boss说小A每统计一次，就给他1RMB。然则，这工作实在索然无味，所以小A找到了你，以每题1津巴布韦币的价钱雇佣了你帮他解决这个问题。
输入
第一行一个数字T，表示数据组数。接下来T行每行三个数字L，R，K表示询问。
输出
共T行，每行一个数字，表示询问区间超级数的数目。
样例输入 复制
3
1 100 1
1 100 2
1 100 3
样例输出 复制
9
10
10
提示
三组数据的超级数分别为<1,2,3,4,5,6,7,8,9>，<1,2,3,4,5,6,7,8,9,18>,<1,2,3,4,5,6,7,8,9,27>。
60%的数据满足r-l<=50000；
100%的数据满足1<=l，r<=10^18，k<=1000，T<=10。