Start with any number, say ~25~. Find the sum of the factorial (~N! = N~ factorial ~= 1 \times 2 \times \dots \times N~; ~0! = 1~ by convention) of each of the digits of ~25~: ~2! + 5! = 2 + 120 = 122~. Repeat this procedure (in this case you will get ~1! + 2! + 2! = 1 + 2 + 2 = 5~). Continue summing the factorials of individual digits until your list repeats a number. For example for ~25~ you will get the following list:

$$\displaystyle 25\ 122\ 5\ 120\ 4\ 24\ 26\ 722\ 5044\ \underline{169}\ 363601\ 1454\ \underline{169}$$

At this point you got a repetition (~169~), so your list will repeat forever and you'd might as well stop now. Your list has ~13~ elements.

Write a program that asks the user to enter any number from ~1~ to ~9\,999\,999~ and computes the FACTORIAL SUM LIST until a duplicate number is found. The output for your program should be the length of your list.

Input Specification

Integer numbers, one per line. The end of data is signaled by the number 0.

Output Specification

The length of the FACTORIAL SUM LIST for each number in the input file.

Sample Input

25
0

Sample Output

13