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:
import sys
import math
#sys.stdin=open("input.txt","r")
#sys.stdout=open("output.txt","w")
def ans(n):
    if n<10:
        print(n)
        return
    c=0
    while n>0:
        c=c+(n%10)
        n=n//10
    ans(c)
                
                       
        
   
#####-input-stuff ################

# for _ in range(int(input())):
#     n=input()
#     arr=[]
#     for i in n:
#         arr.append(ord(i)-65)
#     for i in range(2,len(arr)):
#         cal=abs(arr[i-1]+arr[i-2])%26   
#         if arr[i]!=cal:
#             print("NO")
#             break
#     else:
#         print("YES")
n=int(input())
ans(n)