You are given an integer \(n\). On each step, you may subtract one of the digits from the number.

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

Input

• The only input line has an integer \(n\).

Output

• Print one integer: the minimum number of steps.

Constraints

• \(1 \le n \le 10^6\)

Example

Sample input

27

Sample output

5

Note

An optimal solution is \(27 \to 20 \to 18 \to 10 \to 9 \to 0\).