题目描述

小 Z 在草稿纸上列出了很多数，他觉得相邻两位数字差的绝对值不超过 $k$ 的整数特别奇特，称其为 $k$ 紧凑数。

现在小 Z 想知道 $[l,r]$ 内有多少个 $k$ 紧凑数，希望你帮帮他。

输入格式

一行三个整数 $l,r,k$。

输出格式

一行一个整数，表示 $[l.r]$ 内 $k$ 紧凑数的个数。

1 13 1

12

提示

样例解释：$[1,13]$ 内只有 $13$ 不是 $1$ 紧凑数。

对于 $30\%$ 的数据，$r$ − $l \le 10^5$。

对于另外 $30\%$ 的数据，$l=1$，$r$ 为 $10$ 的倍数。

对于 $100\%$ 的数据，$1 \le l \le r \le 10^{18}$，$0 \le k \le 8$。