Removing digits

Given an integer n, you are asked to calculate the minimum number of steps that would be required to get from n to 0. On each step, you are allowed to subtract one of the digits from the number.

Input

The input contains a single integer n (1 ≀ n ≀ ).

Output

The program should print the minimum number of steps we should take to get from n to 0.

Examples

Input
Output
9
1
11
3
27
5

Explanation

  1. 9 β†’ 0 β‡’ 1 step
  1. 11 β†’ 10 β†’ 9 β†’ 0 β‡’ 3 steps
  1. 27 β†’ 20 β†’ 18 β†’ 10 β†’ 9 β†’ 0 β‡’ 5 steps
Β 

Constraints

Time limit: 10 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue