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
from bisect import *
from collections import deque
#from functools import *
#from fractions import Fraction as f
from copy import *	
#from heapq import *
from math import *
from itertools import permutations as prm,product
#from random import *
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 
sys.setrecursionlimit(10**5)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
di=[[-1,0],[1,0],[0,1],[0,-1]]

def fori(n):
	return [fi() for i in range(n)]	
def inc(d,c,x=1):
	d[c]=d[c]+x if c in d else x
def ii():
	return input().rstrip()	
def li():
	return [int(xx) for xx in input().split()]
def fli():
	return [float(x) for x in input().split()]	
def dadd(d,p,val):
	if p in d:
		d[p].append(val)
	else:
		d[p]=[val]		
def gi():	
	return [xx for xx in input().split()]
def gtc(tc,ans):
	print("Case #"+str(tc)+":",ans)	
def cil(n,m):
	return n//m+int(n%m>0)	
def fi():
	return int(input())
def pro(a): 
	return reduce(lambda a,b:a*b,a)		
def swap(a,i,j): 
	a[i],a[j]=a[j],a[i]	
def bits(i,n):
	p=bin(i)[2:]
	return (n-len(p))*"0"+p	
def prec(a,pre):
	for i in a:
		pre.append(pre[-1]+i)
	pre.pop(0)	
def YN(flag):
	print("YES" if flag else "NO")	
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())			
def gh():
	sys.stdout.flush()
def isvalid(i,j,n,m):
	return 0<=i<n and 0<=j<m 
def bo(i):
	return ord(i)-ord('a')	
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)



t=1
INF=10**18
uu=t



while t>0:
	t-=1
	n=fi()
	n%=9
	if n==0:
		n=9	
	print(n)