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 CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;

#define li int64_t

li calc_sum(li a){
	li sum = 0;
	while(a!=0){
		sum+=a%10;
		a/=10;
	}
	return sum;
}
int main()
{
	li a;
	cin>>a;
	while(a>=10){
		li temp = a;
		a = calc_sum(temp);
	}
	cout<<a<<endl;
}