Рудольф решил таки сменить сотового оператора и перейти на Минифон. Это единственный оператор, у которого можно выбрать телефонный номер любой длины, не превышающей 10³. К сожалению, длина — это единственное, что можно выбрать. Сами номера генерируются из некоторого стартового номера посредством выполнения следующей операции: i-я цифра очередного j-го номера телефона будет равна цифровому корню суммы первых i цифр (j - 1)-го номера телефона. Цифровой корень любой цифры равен этой цифре. Цифровой корень любого числа равен цифровому корню суммы его цифр. Например, цифровой корень числа 65536 равен 7, потому что 6 + 5 + 5 + 3 + 6 = 25 и 2 + 5 = 7. Стартовый номер считается первым.

Рудольф знает стартовый номер, на основе которого сотовый оператор генерирует все номера телефонов, а также порядковый номер своего номера телефона. И ему стало интересно, сколько цифр каждого вида суммарно содержится в первых K номерах. Помогите Рудольфу ответить на этот вопрос.