C3. Великий календарь Июйля
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

И снова наступает очередной Конец Света! На этот раз во всем виноват календарь племени Июйля.

Бобры этого племени знали толк в математике. Археологу Умному Бобру досталась священная скрижаль с магическим числом. Перевод со старобобруйского гласит:

«Да снизойдет на тебя благодать Великого Бобра, да раскроются чакры твои, да не ослепнет третий глаз твой от созерцания Истины! Возьми магическое число, вычти из него любую цифру, которая входит в написание этого числа и получи новое магическое число. Повтори эту операцию до тех пор, пока очередное магическое число не обратится в ноль. Сколько вычитаний сделаешь, столько и будет Земля стоять на Трех Бобрах!»

Очевидно, что при разной последовательности вычитаний можно получить различное количество операций. Но Умный Бобер готовится к худшему и просит рассчитать наименьшее количество операций, которое потребуется для обращения магического числа в ноль.

Входные данные

В единственной строке задано целое магическое число n, 0 ≤ n.

  • для получения 20 баллов требуется решить задачу при n ≤ 106 (подзадача C1);
  • для получения 40 баллов требуется решить задачу при n ≤ 1012 (подзадачи C1+C2);
  • для получения 100 баллов требуется решить задачу при n ≤ 1018 (подзадачи C1+C2+C3).
Выходные данные

Выведите одно число — наименьшее количество вычитаний, которое обратит магическое число в ноль.

Примеры
Входные данные
24
Выходные данные
5
Примечание

Пояснение к примеру. Наименьшее количество операций достигается следующей последовательностью вычитаний:

24 → 20 → 18 → 10 → 9 → 0