UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2063. 我爸是李刚

统计 下载数据

Description

背景: LC同学在2011年的浙江省选中轻松虐爆了WJMZBMR,无压力进入省队并参加了NOI 2011,在1个小时之后,A光了所有题目的LC同学轻松的喝着茶,哼着小曲。 由于在信息学方面的杰出表现以及LC同学的父亲是伟大的LG同志。 LC同学轻松获得了2012年诺亚方舟的船票。并且得到了卖票员这一肥差。 题目描述: 卖票员这一工作十分简单,世界上有很多卖票员。LC同学分到了第L号票到第R号票。 因为一些神奇的东西,第I号票对应的船舱能坐的人恰好是I的各位数字之和。 地球上有很多大家族,每个家族都有M个人,同时每个家族都想买一些连续的票位使他们家族的人都能坐的上船。 大家族都很排外,不肯跟别人共享一张票对应的船舱。 LC同学想知道他在把票都卖光的情况下,能 服务几个大家族呢?

Input

一行三个数L,R,M

Output

一行一个数表示结果。

Sample Input

40 218 57

Sample Output

29

Hint

100%的数据 l,r<=10^18 ,M<=1000 50%的数据,r-l<=10^6

Source

和谐社会模拟赛 Sgu390