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 CF1505B extends PrintWriter {
	CF1505B() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF1505B o = new CF1505B(); o.main(); o.flush();
	}

	int sum(int a) {
		return a < 10 ? a : sum(a / 10) + a % 10;
	}
	int root(int a) {
		while (a >= 10)
			a = sum(a);
		return a;
	}
	void main() {
		int a = sc.nextInt();
		println(root(a));
	}
}