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

#define ll long long
#define vi vector<int>
#define vvi vector<vector<int> >
#define vll vector<long long>
#define vvll vector<vector<long long> >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair


int main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	ll a; cin>>a;
	while(a>9){
		ll sm=0;
		while(a>0){
			sm+=(a%10);
			a/=10;
		}
		a=sm;
	}
	cout<<a<<endl;

}
### Prompt

Please provide a cpp coded solution to the problem described below:

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

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector<int>
#define vvi vector<vector<int> >
#define vll vector<long long>
#define vvll vector<vector<long long> >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair


int main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	ll a; cin>>a;
	while(a>9){
		ll sm=0;
		while(a>0){
			sm+=(a%10);
			a/=10;
		}
		a=sm;
	}
	cout<<a<<endl;

}
```