e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Dynamic Programming - Linear

Removing Digits

You are given an integer n. On each step, you may subtract from it any one-digit number that appears in it.

How many steps are required to make the number equal to 0?

Input

One integer n (1n106).

Output

Print one integer: the minimum number of steps.

Explanation

An optimal solution is 2720181090.

Time limit 1 second
Memory limit 128 MiB
Input example #1
27
Output example #1
5