Summing Digits

For a positive integer n, let f(n) denote the sum of the digits of n when represented in base 10. It is easy to see that the sequence of numbers n, f(n), f(f(n)), f(f(f(n))), … eventually becomes a single-digit number that repeats forever. Let this single digit be denoted by g(n).

For example, consider n = 1234567892. Then:

f(n) = 1+2+3+4+5+6+7+8+9+2 = 47
f(f(n)) = 4+7 = 11
f(f(f(n))) = 1+1 = 2

Therefore, g(1234567892) = 2.

Input Specification

Each line of the input contains a single positive integer n, which is at most 2 000 000 000. The input is terminated by n = 0, which should not be processed.

Output Specification

For each integer of the input, you are to output a single line containing g(n).

Sample Input

1. 2
2. 11
3. 47
4. 1234567892
5. 0

download as text file

Output for Sample Input

1. 2
2. 2
3. 2
4. 2

download as text file