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:
# Uses python3
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)
	

# call the main method 
if __name__ == "__main__": 
	main()