Digital Root

Interview

Time limit1sMemory limit128 MB

Summary

Given positive integers up to 1000 digits, each line until a terminating 0, print the digital root of each number.

Level: Easy3 of 10
Topics: Math, Number theory, String, Implementation
Solved: No attempts yet

Problem

The digital root of a positive integer $N$ is computed as follows. First, add up all of the digits of $N$ . If the resulting sum is a single-digit number, that value is the digital root of $N$ . If it has two or more digits, add up all of its digits again, and repeat this process until a single-digit number is obtained.

For example, consider the digital root of $24$ . Since $2 + 4 = 6$ and $6$ is a single digit, the digital root of $24$ is $6$ . For $39$ , we have $3 + 9 = 12$ , which has two digits, so we add its digits once more. This gives $1 + 2 = 3$ , so the digital root is $3$ .

Given a positive integer $N$ , write a program that computes its digital root.

Input

Positive integers are given one per line. Each integer has at most $1000$ digits. The last line of the input is $0$ , which only marks the end of the input and must not be processed.

Output

For each positive integer in the input, print its digital root on its own line, in the same order as the input.

Examples2

Example 1
Input
```
24
39
0
```
Expected output
```
6
3
```
Example 2
Input
```
1
0
```
Expected output
```
1
```