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.StringTokenizer;
 
public class B {
 
    public void solve() {
        String s = in.next();
 
        int total = Integer.parseInt(s);
        while (Integer.parseInt(s) >= 10) {
            total = 0;
            for (int i = 0; i < s.length(); i++) {
                total += Integer.parseInt(s.charAt(i) + "");
            }
            s = total+"";
        }
 
        out.println(total);
    }
 
    class Pair implements Comparable<Pair> {
        int x;
        int y;
 
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
 
 
        @Override
        public int compareTo(Pair o) {
            if (this.x == o.x)
                return this.y - o.y;
            return this.x - o.x;
        }
 
        @Override
        public String toString() {
            return "Pair{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }
 
    public long binaryPower(long x, int exp, long mod) {
        if (exp == 0)
            return 1;
 
        long result = binaryPower(x, exp / 2, mod);
 
        if (exp % 2 == 0)
            return result * result % mod;
 
        return result * result % mod * x % mod;
    }
 
    String input = "";
    String output = "";
    FastScanner in;
    PrintWriter out;
 
    void run() throws Exception {
        if (input.length() == 0) {
            in = new FastScanner(System.in);
        } else {
            in = new FastScanner(new File(input));
        }
        if (output.length() == 0) {
            out = new PrintWriter(System.out);
        } else {
            out = new PrintWriter(new File(output));
        }
 
        solve();
 
        out.close();
 
    }
 
    public static void main(String[] args) throws Exception {
        new B().run();
    }
 
    class FastScanner {
 
        BufferedReader bf;
        StringTokenizer st;
 
        public FastScanner(InputStream is) {
            bf = new BufferedReader(new InputStreamReader(is));
        }
 
        public FastScanner(File fr) throws FileNotFoundException {
            bf = new BufferedReader(new FileReader(fr));
        }
 
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens()) {
                    st = new StringTokenizer(bf.readLine());
                }
            } catch (IOException ex) {
                ex.printStackTrace();
            }
            return st.nextToken();
        }
 
        public int nextInt() {
            return Integer.parseInt(next());
        }
 
        public long nextLong() {
            return Long.parseLong(next());
        }
 
        public double nextDouble() {
            return Double.parseDouble(next());
        }
 
        public int[] readIntArray(int length) {
            int arr[] = new int[length];
            for (int i = 0; i < length; i++)
                arr[i] = nextInt();
            return arr;
        }
    }
}