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

Solution:
import java.io.*;
import java.util.*;

public class Codeforces
{
    public static void main(String args[])throws Exception
    {
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        char s[]=bu.readLine().toCharArray();
        int i;
        int a=0;
        for(i=0;i<s.length;i++)
        a+=s[i]-'0';
        while(true)
        {
            int x=0,a2=a;
            while(a>0)
            {
                x+=a%10;
                a/=10;
            }
            if(x==a2) {a=a2; break;}
            a=x;
        }
        System.out.println(a);
    }
}