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** (**1** ≤ **n** ≤ `10`

).^{6}

#### Output

Print one integer: the minimum number of steps.

#### Explanation

An optimal solution is **27** → **20** → **18** → **10** → **9** → **0**.

Input example #1

27

Output example #1

5