Description

Given a number, we can form a number chain by

1. arranging its digits in descending order
2. arranging its digits in ascending order
3. subtracting the number obtained in (2) from the number obtained (1) to form a new number
4. and repeat these steps unless the new number has already appeared in the chain

Note that 0 is a permitted digit. The number of distinct numbers in the chain is the length of the chain.

You are to write a program that reads numbers and outputs the length of the chain for each number read.


For example:

Input: 123456789
1. 987654321 - 123456789 = 864197532
2. 987654321 - 123456789 = 864197532
Chain length = 2
You should output: 2

Input: 1234
1. 4321 - 1234 = 3087
2. 8730 - 378 = 8352
3. 8532 - 2358 = 6174
4. 7641 - 1467 = 6174
Chain length = 4
You should output: 4

Input: 444
1. 444 - 444 = 0
2. 0 - 0 = 0
Chain length = 2
You should output: 2

Input

The input consists of a sequence of positive numbers, all less than  , each on its own line, terminated by 0. The input file contains at most 10 numbers.

Output

The output only have to print the chain length, no chain will contain more than 1000 distinct numbers.
Note that there is a '\n' at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss