三段整除密码

题目描述

一个五位正整数可以产生三个连续的三位片段。

例如，整数 12345 的三个片段分别为：

• 前三位：123；
• 中间三位：234；
• 后三位：345。

给定五位整数区间 [L,R] 和正整数 K，请统计区间中有多少个整数，其三个三位片段都能被 K 整除。

注意：片段允许以数字 0 开头。例如整数 10005 的三个片段数值分别为 100、0、5。

输入格式

输入一行三个整数 L R K。

输出格式

输出一个整数，表示满足条件的五位整数个数。

样例输入

10000 30000 15

样例输出

4

数据范围

对于全部数据：

• 10000 <= L <= R <= 99999；
• 1 <= K <= 1000。