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.*;
import java.lang.*;
import java.util.Random;
public class Main {
    
    public static void main (String[] args) throws java.lang.Exception {
    	Scanner scan = new Scanner (System.in);
        long test = scan.nextLong();
        long num = test;
        while (num>=10) {
            int swap=0;
            while (num>0) {
                swap += num%10;
                num/=10;
            }
            num=swap;
        }
        System.out.println(num);
    }
}