The digital root of a natural number is obtained as follows. Add up all the digits of the given number. The process is repeated until the result is a single-digit number, which is called the digital root of the number.

Input: The input to the program is a natural number n<=10^{9}.