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 g(n).

For example, consider n = 1234567892.

Then:

Therefore, g(1234567892) = 2.

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