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.Scanner;
 
public class DMCA {
 
	public static void main(String[] args) {
		
		try (Scanner sc = new Scanner(System.in)) {
			int x = sc.nextInt();
			int sum = x;
			while (sum / 10 != 0)  {
			    sum = sumDigits(sum);
			}
			System.out.println(sum);
		}
	}
	
	public static int sumDigits (int n) {
	    int sum = 0;
		while (n != 0) {
			sum += (n % 10);
			n /= 10;
		}
		return sum;
	}
}