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 ~N~.

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?

Input Specification

The first line of input contains an integer ~N~ ~(1 \le N \le 10^{18})~, the number that Santa has gifted Danielle.

Output Specification

The minumum number of operations required for Danielle to reduce ~N~ to 1.

Sample Input 1

10

Sample Output 1

2

Sample Input 2

400

Sample Output 2

3