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

public class CodeForces {
	
	static int mod = 1000000007;
	static boolean flag = false;
	static int d = 100001;

	public static void main(String[] args) throws FileNotFoundException {
		FastScanner sc = new FastScanner();
		StringBuilder sb = new StringBuilder();
		int t = 1;//sc.nextInt();
		while (t-- > 0) {
			solve(sc,sb);
		}
		System.out.print(sb);
	}

	private static void solve(FastScanner sc, StringBuilder sb) {
		int n=sc.nextInt();
		while(n>9) {
			int sum=0;
			int tem=n;
			while(tem>0) {
				sum+=tem%10;
				tem/=10;
			}
			n=sum;
		}
		System.out.println(n);
		
	}

	public static void debug(boolean flag, String str) {
		if (flag) {
			System.out.println(str);
		}
	}
}

class Pair implements Comparable<Pair> {
	int first, second;

	Pair(int f, int s) {
		first = f;
		second = s;
	}

	@Override
	public int compareTo(Pair o) {
		if (first == o.first) {
			return second - o.second;
		}
		return first - o.first;
	}

}

class FastScanner {
	BufferedReader br;
	StringTokenizer st;

	public FastScanner() throws FileNotFoundException {
		try {
			File file = new File("src\\input.txt");
			br = new BufferedReader(new FileReader(file));
		} catch (Exception e) {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

	}

	String next() {
		while (st == null || !st.hasMoreElements()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		return st.nextToken();
	}

	int nextInt() {
		return Integer.parseInt(next());
	}

	long nextLong() {
		return Long.parseLong(next());
	}

	double nextDouble() {
		return Double.parseDouble(next());
	}

	int[] nextInts(int N) {
		int[] res = new int[N];
		for (int i = 0; i < N; i++) {
			res[i] = (int) nextLong();
		}
		return res;
	}

	long[] nextLongs(int N) {
		long[] res = new long[N];
		for (int i = 0; i < N; i++) {
			res[i] = nextLong();
		}
		return res;
	}

	public double[] nextDoubles(int N) {
		double[] res = new double[N];
		for (int i = 0; i < N; i++) {
			res[i] = nextDouble();
		}
		return res;
	}

	String nextLine() {
		String str = "";
		try {
			str = br.readLine();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return str;
	}
}