该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P2188 小Z的 k 紧凑数

题目描述

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

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

输入格式

第一行包含三个整数 $l，r，k$。

输出格式

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

输入输出样例 #1

输入 #1

1 13 1

输出 #1

12

说明/提示

【数据规模】

对于 $30$ 的数据，$r − l ≤ 10^5$；

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

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