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.util.*;
import java.awt.image.BandedSampleModel;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.Scanner;
public class C {

    static void sort(int[] A){

        int n = A.length;
        Random rnd = new Random();
        for(int i=0; i<n; ++i){
            int tmp = A[i];
            int randomPos = i + rnd.nextInt(n-i);
            A[i] = A[randomPos];
            A[randomPos] = tmp;
        }
        Arrays.sort(A);
    }

    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        //int cases = sc.nextInt();

        //for(int i=0;i<cases;i++)
        {
            int  x=sc.nextInt();
            int sum=x;
            String s=x+"";
            while(s.length()!=1) {
                sum=0;
                for (int i = 0; i < s.length(); i++) {
                    sum = sum + (s.charAt(i) - '0');


                    //System.out.println(s.charAt(i)-'A'+1);
                }
                s=sum+"";
            }

            System.out.println(sum);
            //System.out.println("YES");
        }

    }
}