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 math 
  
# Returns digital root of num
def digitalRoot(num):
      
    # If num is 0.
    if (num == "0"):
        return 0
  
    # Count sum of digits under mod 9
    ans = 0
    for i in range (0, len(num)):
        ans = (ans + int(num[i])) % 9
          
  
    # If digit sum is multiple of 9, answer
    # 9, else remainder with 9.
    if(ans == 0):
        return 9
    else: 
        return ans % 9
  
# Driver method
num = input()
  
# Calling digitalRoot function
print (digitalRoot(num))