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.*;
 
public class Is_it_rated_2 {
   
	 static long digroot(long n)
	    {
	        long root = 0;
	   
	        while (n > 0 || root > 9) 
	        {
	             if (n == 0) {
	                n = root;
	                root = 0;
	            }
	              
	            root += n % 10;
	            n /= 10;
	        }
	        return root;
	    }
    public static void main(String[] args)
    {
       Scanner sc=new Scanner(System.in);
     long n=sc.nextLong();
     System.out.println(digroot(n));
sc.close();
    }

}