Problem: Many people are aware of DMCA – Digital Millennium Copyright Act. But another recently proposed DMCA – Digital Millennium Calculation Act – is much less known.

In this problem you need to find a root of a number according to this new DMCA law.

Input

The input contains a single integer a (1 ≤ a ≤ 1000000).

Output

Output the result – an integer number.

Examples

Input


1


Output


1


Input


81


Output


9

Solution (in PYTHON3):

Solution:
n=int(input())
sum1=0
while(n>0 or sum1>9):
    if(n!=0):
        rem=n%10
        sum1=sum1+rem
        n=n//10
    elif(sum1>9):
        n=sum1
        sum1=0
print(sum1)