小Z的 k 紧凑数

题目描述

小 Z 在草稿纸上列出了很多数,他觉得相邻两位数字差的绝对值不超过 k 的整数特别奇特,称其为 k 紧凑数。 现在小 Z 想知道 [l,r] 内有多少个 k 紧凑数,希望你帮帮他。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #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。