Repeated Addition

Given a positive integer n, sum all of its digits to get a new number. Repeat this operation until the new number is less than 10 and return it.

Constraints

• 1 ≤ n < 2 ** 31

https://binarysearch.com/problems/Repeated-Addition

Examples

Example 1

Input

• n = 8835

Output

• answer = 6

Explanation

• 8 + 8 + 3 + 5 = 24
• 2 + 4 = 6

Solution