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 PYTHON):

Solution:
from fractions import Fraction as F
import math
import sys
import random
import time

random.seed(time.time())

fi = sys.stdin
fo = sys.stdout
fe = sys.stderr
exit = sys.exit

readline = raw_input

def readargs(tp=None):
	if tp is not None:
		return map(tp, readline().split())
	return readline().split()

def yesno(flag, yes='', no=''):
	if flag:
		print yes if yes else 'YES'
	else:
		print no if no else 'NO'

truefalse = lambda flag : yesno(flag, yes='TRUE', no='FALSE')

n = readline().strip()
while len(n) > 1:
    n = str(sum(map(int, n))) 
print n

#    if n == 1:
#        print 1
#        continue
#
#    found = False
#
#    for i in range(2, 20):
#        j = 2
#        while True:
#            cur = j ** i
#            if cur == n:
#                print j
#                found = True
#                break
#            if cur > n:
#                break
#            j += 1
#        if found:
#            break
#
#    if not found:
#        print n