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:
#!/usr/bin/python3
# -*- coding: utf-8 -*-


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()