Counting k-Compact Numbers

Counting \(k\)-Compact Numbers

A positive integer is called a \(k\)-compact number if for every pair of adjacent digits \(d_i\) and \(d_{i+1}\) in its decimal representation, the following condition holds:

$$|d_i-d_{i+1}| \le k.$$

Given an interval \([l, r]\) and an integer \(k\), your task is to count how many \(k\)-compact numbers lie within that interval.

inputFormat

The input consists of three space-separated integers: \(l\), \(r\), and \(k\). Here, \(l\) and \(r\) define the interval \([l, r]\) and \(k\) is the maximum allowed absolute difference between any two adjacent digits.

outputFormat

Output a single integer representing the number of \(k\)-compact numbers in the interval \([l, r]\).

sample

10 15 1

3