Danielle loves numbers and has asked Santa to get her the number one, her favourite number, for Christmas. Santa has obliged with this request, however he has "wrapped" the number mathematically, instead giving her some number .
Danielle can unwrap the number by repeatedly performing one of the following two operations:
- Subtract 1 from the number
- Divide the number by the sum of its digits (rounding down if necessary)
Danielle wants to get her present as soon as possible, so she wonders: what is the minimum number of operations required to fully unwrap her number?
The first line of input contains an integer , the number that Santa has gifted Danielle.
The minumum number of operations required for Danielle to reduce to 1.
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2