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.*;


import java.io.*;
 
public class test{
	
	public static void main(String[] args) throws Exception {
		Scanner sc=new Scanner(System.in);
		PrintWriter pw=new PrintWriter(System.out);
		String st=sc.next();
		while(st.length()>1) {
			int x=0;
			for(int i=0;i<st.length();i++) x+=(st.charAt(i)-'0');
			st=x+"";
		}
		pw.print(st);
        pw.flush();
        pw.close();
	}
	static class tuble{
		int u,v,w;
		public tuble(int u,int v,int w) {
			this.u=u; this.v=v; this.w=w;
		}
		public String toString() {
			return u+" "+v+" "+w;
		}
	}
}