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.security.KeyPair;
import java.util.*;

public class Main
{
    public static void main(String[] args) throws IOException {
        OutputStream outputStream = System.out;
        FastReader in = new FastReader();
        PrintWriter out = new PrintWriter(outputStream);
        PROBLEM solver = new PROBLEM();
        int t=1;
        //t = in.nextInt();
        for(int i=0;i<t;i++){
            solver.solve(in, out);
        }
        out.close();
    }
    static class PROBLEM
    {
        public void solve(FastReader in,PrintWriter out)
        {

            int n = in.nextInt();
            int y = n;

            int sum = 0;

            while(true) {
                while (y > 0) {
                    sum += y % 10;
                    y /= 10;
                    if(y == 0){
                        if(sum >= 10) {
                            y = sum;
                            sum = 0;
                        }else{
                            break;
                        }
                    }
                }
                break;
            }

            out.println(sum);


        }
    }



    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        char nextChar() {
            return next().charAt(0);
        }

        boolean nextBoolean() {
            return !(nextInt() == 0);
        }
        // boolean nextBoolean(){return Boolean.parseBoolean(next());}

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

    }

    private static int[] mergeSort(int[] array){

        if(array.length <= 1){
            return array;
        }

        int midpoint = array.length / 2;

        int[] left = new int[midpoint];
        int[] right;

        if(array.length % 2 == 0){
            right = new int[midpoint];
        }else{
            right = new int[midpoint + 1];
        }

        for (int i = 0; i < left.length; i++) {
            left[i] = array[i];
        }

        for (int i = 0; i < right.length; i++) {
            right[i] = array[i + midpoint];
        }

        int[] result = new int[array.length];

        left = mergeSort(left);
        right = mergeSort(right);

        result = merge(left, right);

        return result;
    }

    private static int[] merge(int[] left, int[] right){

        int[] result = new int[left.length + right.length];
        int leftPointer = 0, rightPointer = 0, resultPointer = 0;

        while(leftPointer < left.length || rightPointer < right.length){

            if(leftPointer < left.length && rightPointer < right.length){

                if(left[leftPointer] < right[rightPointer]){
                    result[resultPointer++] = left[leftPointer++];
                }else{
                    result[resultPointer++] = right[rightPointer++];
                }
            }else if(leftPointer < left.length){
                result[resultPointer++] = left[leftPointer++];
            }else{
                result[resultPointer++] = right[rightPointer++];
            }
        }
        return result;
    }
}