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

Difficulty: MEDIUM_HARD
Tags: Number theory

Implementation

Starter code:

Solutions:
n = int(input())
sumo = n
while n >= 10:
	sumo = 0
	while n != 0:
		sumo += n % 10
		n //= 10
	n = sumo
print(sumo)


n = int(input())

def f(n):
	ret = 0
	for i in str(n):
		ret += int(i)
	return ret
while n > 9:
	n = f(n)
print(n)


n = int(input())
if n % 9 == 0:
	print(9)
else:
	print(n % 9)


from sys import stdin, stdout
import sys
import math
import itertools
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)

def main():
	s = input().strip()
	while len(s) > 1:
		sum = 0
		for i in s:
			sum += int(i)
		s = str(sum)
	print(s)
main()


n = int(input())
print(int((n - 1) % 9 + 1))


t = int(input())
if t % 9 == 0:
	print(9)
else:
	print(t - t // 9 * 9)


import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
try:
	(sys.stdin, sys.stdout) = (open('in.txt', 'r'), open('out.txt', 'w'))
except:
	pass
ii1 = lambda : int(sys.stdin.readline().strip())
is1 = lambda : sys.stdin.readline().strip()
iia = lambda : list(map(int, sys.stdin.readline().strip().split()))
isa = lambda : sys.stdin.readline().strip().split()
mod = int(1000000000.0 + 7)
from collections import *
from math import *
from collections import deque as dq
s = is1()
ans = 0
for i in s:
	ans += int(i)
while len(str(ans)) > 1:
	new = 0
	for i in str(ans):
		new += int(i)
	ans = new
	new = ''
print(ans)


import math
num = input()
sum = 0
while len(num) > 1:
	for i in num:
		sum += int(i)
	num = str(sum)
	sum = 0
print(num)


n = int(input())

def root(n):
	if n // 10 == 0:
		return n
	return root(sum((int(i) for i in str(n))))
print(root(n))


n = input()
a = [int(i) for i in n]
ans = sum(a)
while ans > 9:
	a = [int(i) for i in str(ans)]
	ans = sum(a)
print(ans)


x = int(input())

def digit_sum(n):
	if n < 10:
		return n
	return n % 10 + digit_sum(n // 10)

def digit_root(n):
	if n < 10:
		return n
	return digit_root(digit_sum(n))
print(digit_root(x))


dig_sum = lambda x: sum(map(int, x))
i = dig_sum(input())
while i > 9:
	i = dig_sum(str(i))
print(i)


n = int(input())

def somme(n):
	l = map(int, list(str(n)))
	return sum(l)
while n >= 10:
	n = somme(n)
print(n)


import math

def digitalRoot(num):
	if num == '0':
		return 0
	ans = 0
	for i in range(0, len(num)):
		ans = (ans + int(num[i])) % 9
	if ans == 0:
		return 9
	else:
		return ans % 9
num = input()
print(digitalRoot(num))


s = input()
while len(s) != 1:
	s = str(sum([int(i) for i in s]))
print(s)


n = input().strip()
while len(n) > 1:
	x = 0
	for c in n:
		x += int(c)
	n = str(x)
print(n)


def sum(n):
	x = n
	n = ''
	sum = 0
	for i in x:
		sum += int(i)
	n = str(sum)
	return n
n = input()
while len(n) != 1:
	n = sum(n)
print(n)


x = int(input())

def f(x):
	res = 0
	while x > 0:
		res += x % 10
		x //= 10
	if res < 10:
		return res
	else:
		return f(res)
print(f(x))


import time
import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string, heapq as h
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def getInt():
	return int(input())

def getStrs():
	return input().split()

def getInts():
	return list(map(int, input().split()))

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def getBin():
	return list(map(int, list(input())))

def isInt(s):
	return '0' <= s[0] <= '9'

def ceil_(a, b):
	return a // b + (a % b > 0)
MOD = 10 ** 9 + 7

def solve():
	N = getInt()
	while len(str(N)) > 1:
		N = sum([int(s) for s in str(N)])
	return N
print(solve())


a = int(input())
print((a - 1) % 9 + 1)


def digit_sum(x: int, b: int) -> int:
	total = 0
	while x > 0:
		total = total + x % b
		x = x // b
	return total

def digital_root(x: int, b: int) -> int:
	seen = set()
	while x not in seen:
		seen.add(x)
		x = digit_sum(x, b)
	return x
digit = int(input())
print(digital_root(digit, 10))


def reduce(x):
	r = 0
	while x:
		r += x % 10
		x //= 10
	return r
n = int(input())
while n > 9:
	n = reduce(n)
print(n)


(N,) = [int(x) for x in input().split()]
while len(str(N)) != 1:
	N = sum((int(d) for d in str(N)))
print(N)


def func(string):
	sum = 0
	for i in string:
		sum += int(i)
	if len(str(sum)) > 1:
		return func(str(sum))
	return sum
a = input()
print(func(a))


n = str(input())
while len(n) != 1:
	s = 0
	for i in range(len(n)):
		s += int(n[i])
	n = str(s)
print(n)


import sys
INP = lambda : sys.stdin.readline().strip()
INT = lambda : int(INP())
MAP = lambda : map(int, INP().split())
ARR = lambda : [int(i) for i in INP().split()]

def JOIN(arr, x=' '):
	return x.join([str(i) for i in arr])

def EXIT(x='NO'):
	print(x)
	exit()
x = INP()
while len(x) > 1:
	x = str(sum([int(i) for i in x]))
print(x)


def croot(s):
	s = list(s)
	s = list(map(int, s))
	s = sum(s)
	return str(s)
s = input()
while len(s) > 1:
	s = croot(s)
print(s)


x = int(input())
if x % 9 == 0:
	print(9)
else:
	while True:
		y = 0
		while x > 0:
			if x % 10 == 9:
				x = x // 10
			else:
				y += x % 10
				x = x // 10
		if y >= 1 and y <= 9:
			break
		x = y
	print(y)


import math
n = input()
while len(n) >= 2:
	n = list(map(int, n))
	n = str(sum(n))
print(n)


a = input()
while len(a) > 1:
	a = str(sum((int(x) for x in a)))
print(a)


from itertools import product
import itertools
import sys
import heapq
from collections import deque
MOD = 1000000000007

def find(parent, i):
	if parent[i] != i:
		parent[i] = find(parent, parent[i])
	return parent[i]

def union(parent, rank, xx, yy):
	x = find(parent, xx)
	y = find(parent, yy)
	if rank[x] > rank[y]:
		parent[y] = x
	elif rank[y] > rank[x]:
		parent[x] = y
	else:
		parent[y] = x
		rank[x] += 1
ans = 0
K = int(sys.stdin.readline().strip())
K = K % 9
if K == 0:
	K = 9
print(K)


a = int(input())

def main(a):
	if len(a) == 1:
		return a
	return main(str(sum([int(i) for i in a])))
print(main(str(a)))


inp = int(input())
if inp % 9 == 0:
	res = 9
	print(res)
else:
	res = inp % 9
	print(res)


def f(n):
	if n < 10:
		return n
	else:
		return n % 10 + f(int(n / 10))
x = int(input())
while x >= 10:
	x = f(x)
print(x)


a = input()
while len(a) > 1:
	a = str(sum(map(int, a)))
print(a)


from sys import stdin
n = int(stdin.readline())
print((n - 1) % 9 + 1)


root = int(input())
while root >= 10:
	a = 0
	b = root
	while b > 0:
		a += b % 10
		b //= 10
	root = a
print(root)


n = int(input())
while n >= 10:
	n = sum((int(i) for i in str(n)))
print(n)


a = input()
while len(a) != 1:
	a1 = 0
	for ch in a:
		a1 += int(ch)
	a = str(a1)
print(a)


func = lambda x: str(sum(list(map(int, list(x)))))
a = input()
while len(a) > 1:
	a = func(a)
print(a)


def digit_root(n):
	s = str(n)
	m = sum((int(char) for char in s))
	if m < 10:
		return m
	else:
		return digit_root(m)
n = int(input())
print(digit_root(n))


import sys
from bisect import *
from collections import deque
from copy import *
from math import *
from itertools import permutations as prm, product

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)


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)


n = int(input())
while n >= 10:
	n = sum([int(x) for x in str(n)])
print(n)


a = [int(x) for x in list(input())]
while sum(a) > 9:
	a = [int(x) for x in list(str(sum(a)))]
print(sum(a))


N = input()
while len(N) > 1:
	N = str(sum((int(elt) for elt in N)))
print(N)


def digitalRoot(num):
	num = sum(list(map(int, list(str(num)))))
	if len(str(num)) == 1:
		return num
	else:
		return digitalRoot(num)
num = int(input())
print(digitalRoot(num))


num = input()
ans = 10
while ans > 9:
	ans = 0
	for ch in num:
		ans += ord(ch) - ord('0')
	if ans > 9:
		num = str(ans)
print(ans)


def main():
	num = int(input())
	while len(str(num)) > 1:
		arr = [int(x) for x in str(num)]
		num = sum(arr)
	print(num)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _aa in range(1):
	main()


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
n = inp()
n %= 9
if n == 0:
	n = 9
pr(n)


a = tuple(map(int, input()))
while len(a) > 1:
	a = tuple(map(int, str(sum(a))))
print(a[0])


import math
x = int(input())
ans = 0
while True:
	while x > 0:
		ans += x % 10
		x //= 10
	if ans > 9:
		(ans, x) = (0, ans)
	else:
		break
print(ans)


print((int(input()) - 1) % 9 + 1)


from sys import stdin, gettrace
if gettrace():

	def inputi():
		return input()
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def main():
	a = int(input())
	while a >= 10:
		b = a
		a = 0
		while b > 0:
			a += b % 10
			b //= 10
	print(a)
main()


def solve():
	s = input()
	lenth = len(s)
	while True:
		if lenth == 1:
			print(s)
			return
		sum = 0
		for i in range(lenth):
			sum = sum + ord(s[i]) - ord('0')
		s = str(sum)
		lenth = len(s)
solve()


n = int(input())
s = sum(map(int, str(n)))
while s >= 10:
	s = sum(map(int, str(s)))
print(s)


import math
import sys

def main():
	x = sum((int(c) for c in sys.stdin.readline().strip()))
	while x >= 10:
		x = sum((int(c) for c in str(x)))
	print(x)
main()


n = int(input())
while n >= 10:
	b = 0
	while n > 0:
		s = n % 10
		n = (n - s) // 10
		b += s
	n = b
print(n)


x = int(input())
while x >= 10:
	x = sum((int(d) for d in str(x)))
print(x)


n = input()
while len(n) > 1:
	q = sum(map(int, n))
	n = str(q)
print(n)


n = int(input())
if n <= 9:
	print(n)
else:
	while n > 9:
		m = n
		s = 0
		while m != 0:
			a = m % 10
			s += a
			m = m // 10
		n = s
	print(s)


from sys import stdin

def main():
	input = lambda : stdin.readline()[:-1]
	A = input()
	while len(A) > 1:
		A = str(sum(map(int, A)))
	print(A)
main()


import math

def digital_root(num):
	if num < 10:
		return num
	tmp = 0
	while num > 0:
		tmp += num % 10
		num //= 10
	return digital_root(tmp)
while True:
	try:
		num = int(input())
		ans = digital_root(num)
		print(ans)
	except EOFError:
		break


import collections
import math
n = input()
while len(n) > 1:
	n = str(sum([ord(c) - ord('0') for c in str(n)]))
print(n)


def solve(n):
	if n > 9:
		return solve(sum([int(i) for i in str(n)]))
	return n
a = int(input())
print(solve(a))


n = int(input())
while n > 9:
	u = str(n)
	s = 0
	for x in u:
		s += int(x)
	n = s
print(n)


n = int(input())
while n > 9:
	s = str(n)
	n = sum(map(int, list(s)))
print(n)


a = list(map(int, list(input())))
ans = sum(a) % 9
if ans == 0:
	print(9)
else:
	print(ans)


n = int(input())
while n >= 10:
	n = sum(list(map(lambda x: int(x), list(str(n)))))
print(n)


x = int(input())
sum = x
while sum >= 10:
	sum = 0
	while x > 0:
		sum = sum + x % 10
		x = x // 10
	x = sum
print(sum)


import sys
import math

def ans(n):
	if n < 10:
		print(n)
		return
	c = 0
	while n > 0:
		c = c + n % 10
		n = n // 10
	ans(c)
n = int(input())
ans(n)


def maissa(myinput):
	aa = str(myinput)
	while len(aa) != 1:
		result = 0
		for i in range(len(aa)):
			result = result + int(aa[i])
		aa = str(result)
	return int(aa)
t = int(input())
print(maissa(t))


import math
i = int(input())
while i >= 10:
	s = list(str(i))
	i = 0
	for x in s:
		i += int(x)
print(i)


a = input()
while len(a) > 1:
	a = str(sum((int(c) for c in a)))
print(a)