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 Solve {

    static Scanner scan = new Scanner(System.in);

    public static int ceil(int x,int y){
        return (x+y-1)/y;
    }

    public static void solve(int n,int sum){
        System.out.println(ceil(sum,4));
    }

    public static void main(String[] args) {



        int n = scan.nextInt();

        System.out.println((n-1)%9+1);
//        int[] s = new int[n];
//        int sum = 0;
//        for(int i=0;i<n;i++){
//            s[i] = scan.nextInt();
//            sum+=s[i];
//        }
//
//        solve(n,sum);


    }
}