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 codefapril1{
	
public static void main(String args[]){

		Scanner sc=new Scanner(System.in);
	
		String s=sc.nextLine();
		
		String p=s;
		
		while(true)
		{	
			int a=0;
			
			if(p.length()==1)
				break;
			
			for(int i=0;i<p.length();i++)
			{
				a+=Integer.parseInt(String.valueOf(p.charAt(i)));
			}
			
			p=Integer.toString(a);
			
		}
		
		System.out.println(p);
	}
}