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.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.io.*;

public class Main {
    

    public static void main(String args[]) throws IOException {
        Scanner in=new Scanner(System.in);
        try {
            int n=in.nextInt();
            int s=0;
            s=n;
            while(s>9)
            {
                n=s;
                s=0;
                while(n>0)
                {
                    s+=n%10;
                    n=n/10;
                }
            }
            System.out.println(s);
            // long n=in.nextInt();
            // long ans=(long)Math.sqrt(n);
            // System.out.println(ans);
            // String s=in.next();
            // int l=s.length();
            // int c1=0,c2=0;
            // String ans="YES";
            // if(l>2)
            // {
            //     c1=s.charAt(0)-65;
            //     c2=s.charAt(1)-65;
            //     for (int i=2;i<l ;i++ )
            //     {
            //         int c=s.charAt(i);
            //         if((c-65)!=(c1+c2)%26)
            //         {
            //             // System.out.println(c1);
            //             // System.out.println(c2);
            //             // System.out.println(c);
            //             ans="NO";
            //             break;
            //         }
            //         c1=c2;
            //         c2=c-65;
            //     }
            // }
            // long t = in.nextLong();
            // // long t=in.nextLong();
            // // String st = sc.readLine();
            // // int l=st.length();
            // // HashSet<String> h=new HashSet<String>();
            // // StringBuilder a=new StringBuilder();
            // // System.out.println();

            // while (t > 0) {
            //     t--;
            //     // solve();
            //     System.out.println();
            // }

        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    // private static void solve() {

    // }
}