Вы проходите собеседование в легендарную команду "Отбой". Вы успешно отвечали на все вопросы, и теперь от главного приза - членства в команде "Отбой", дающего доступ к безлимитным запасам кефирчика, вас отделяет последняя задача - посчитать количество чисел на отрезке с l по r, сумма цифр которых кратна числу k.

Более формально: Вам следует посчитать количество чисел i (l ≤ i ≤ r), у которых сумма цифр кратна k.

Input

Three integers l, r and k (1 ≤ l ≤ r ≤ 1018, 1 ≤ k ≤ 1000).

Output

Print the required amount of numbers.