#include <iostream>
#include <fstream>
#include <cmath>
#include <random>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <functional>
#include <typeinfo>

#include <vector>
#include <array>
#include <valarray>
#include <queue>
#include <stack>
#include <set>
#include <map>
 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cassert>

#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll unsigned long long
#define mk make_pair
#define pl pair<ll, ll> 
#define llv vector<ll>
#define pv vector<pair<ll,ll> >
#define pb(w) push_back(w)
#define  ppb(w,z) push_back({w,z})
#define ff first
#define ss second
#define sz size()
const int M = 1e9+7, N =1e7+3;
using namespace std;
int main(){
	ll a ,  c,  s,  m;
	cin>>a;
	
	if (a<9) {cout<<a; return 0;}
	else {
		s=a;
	while (s>9){
		m=s;
		s=0;
		while (m>0){
			s+=m % 10;
			m=m/10;}
              } }
              
          cout<<s;
	return 0;
	
}

### Prompt

In cpp, your task is to solve the following 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

### Response

```cpp
#include <iostream>
#include <fstream>
#include <cmath>
#include <random>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <functional>
#include <typeinfo>

#include <vector>
#include <array>
#include <valarray>
#include <queue>
#include <stack>
#include <set>
#include <map>
 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cassert>

#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll unsigned long long
#define mk make_pair
#define pl pair<ll, ll> 
#define llv vector<ll>
#define pv vector<pair<ll,ll> >
#define pb(w) push_back(w)
#define  ppb(w,z) push_back({w,z})
#define ff first
#define ss second
#define sz size()
const int M = 1e9+7, N =1e7+3;
using namespace std;
int main(){
	ll a ,  c,  s,  m;
	cin>>a;
	
	if (a<9) {cout<<a; return 0;}
	else {
		s=a;
	while (s>9){
		m=s;
		s=0;
		while (m>0){
			s+=m % 10;
			m=m/10;}
              } }
              
          cout<<s;
	return 0;
	
}

```