Interview at "Lights Out"#4149
You are about to join the legendary team "Vidbiy". Having successfully answered all previous challenges, only one task remains between you and the grand prize—membership in the "Vidbiy" team, which grants unlimited supplies of kefir. For your final challenge, determine how many numbers in the range from to have a digit sum divisible by .
More formally: count the number of integers such that l \leq i \leq r and the sum of the digits of is divisible by .
The input consists of three integers , and (1 \leq l \leq r \leq 10^{18}, 1 \leq k \leq 1000).
Output a single integer — the number of numbers that satisfy the condition.
Esempio 1