И снова наступает очередной Конец Света! На этот раз во всем виноват календарь племени Июйля.
Бобры этого племени знали толк в математике. Археологу Умному Бобру досталась священная скрижаль с магическим числом. Перевод со старобобруйского гласит:
«Да снизойдет на тебя благодать Великого Бобра, да раскроются чакры твои, да не ослепнет третий глаз твой от созерцания Истины! Возьми магическое число, вычти из него любую цифру, которая входит в написание этого числа и получи новое магическое число. Повтори эту операцию до тех пор, пока очередное магическое число не обратится в ноль. Сколько вычитаний сделаешь, столько и будет Земля стоять на Трех Бобрах!»
Очевидно, что при разной последовательности вычитаний можно получить различное количество операций. Но Умный Бобер готовится к худшему и просит рассчитать наименьшее количество операций, которое потребуется для обращения магического числа в ноль.
В единственной строке задано целое магическое число n, 0 ≤ n.
Выведите одно число — наименьшее количество вычитаний, которое обратит магическое число в ноль.
24
5
Пояснение к примеру. Наименьшее количество операций достигается следующей последовательностью вычитаний:
Название |
---|