TAP2015H - Hugo s homework

no tags 

[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2015 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wp-content/uploads/2015/09/pruebaTAP2015.pdf ]

Hugo goes to primary school, but he is convinced that not enough homework is being given to him. Specifically, he was recently taught how to subtract two numbers, but each day he is given a single subtraction to perform at home. Hugo knows that in order to master such a complex technique he should practice much more, so he has decided to take matters into his own hands and create his own homework.

It's not easy for Hugo to invent exercises about a subject he does not fully comprehend, so he has devised the following method to perform multiple subtractions. He starts by asking his mother for a number N, and then forms the number M containing the same digits as N in increasing order from left to right, after which he finally performs the subtraction N-M. For example, if his mother chooses the number N = 321 then M = 123 and the subtraction Hugo must perform is N - M = 321-123 = 198.

Hugo wouldn't want to bother his mother too often, so he will repeat this procedure using the result of the subtraction N-M in one step as the number N he starts with in the next step. This will end only when at some point he reaches the value N = 0, as this case is useless to practice subtractions because he would have M = 0: Hugo already knows perfectly well that if he has no candies he cannot eat any candies, and will therefore continue to not have or eat candies forever.

Now Hugo's mother would like to know, given a number N, how many subtractions Hugo can perform if she gives him that number to start his homework. In the previous example, in the second step Hugo would have N = 198 so that M = 189 and N - M = 198 - 189 = 9. Then in the third step N = 9, M = 9 and N - M = 0, so here the fun ends because in the fourth step he would have N = 0. Thus, starting with the number N = 321 Hugo will perform 3 subtractions.

 

Input

There are multiple test cases in the input file. Each test case consists of one line containing an integer N, representing the number Hugo's mother will give him to start his homework (1 ≤ N ≤ 109).

 

Output

For each test case, print one line containing one integer representing the number of subtractions Hugo will perform if he starts his homework with number N.

 

Example

Input:
321
20
960687301

Output:
3
2
91

hide comments
iit2015068: 2015-10-31 08:40:16

Can you explain what happens with 20?
I assume, step1-(20-02=18)
step 2(81-18) or (18-81 as this case gives negative number)

Last edit: 2015-10-31 08:40:51

Added by:Fidel Schaposnik
Date:2015-10-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Argentinian Programming Tournament 2015