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>
#define endline "\n"
#define mod1 1000000007
#define mod2 998244353
#define pb push_back
#define mp make_pair
#define st first
#define nd second

typedef long long ll;
using namespace std;
const ll INF = 1e18L;

ll t=1,n,m,k,bruh;

void solve(){
	cin>>n;
	while(n>0){
		m+=n%10;n/=10;
	}
	while(m>0){
		k+=m%10;m/=10;
	}
	while(k>0){
		bruh+=k%10;k/=10;
	}
	cout<<bruh;
}

int main(){
	//freopen("roads.gir","r",stdin);
	//freopen("roads.cik","w",stdout);
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	//cin>>t;
	while(t--)solve();
	return 0;
}