//CF: Ankit Singh

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

#define     prec(n)         fixed<<setprecision(n)
#define     int             long long int
#define     fast()          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)          begin(x),end(x)
#define     rz(x)           resize(x)
#define     asn(x,y)        assign(x,y)
#define     mem(a,b)        memset(a,b,sizeof(a))
#define     sz(x)           ((int)size(x))
#define     eb              emplace_back
#define     pb              push_back
#define     pf              push_front
#define     pob             pop_back
#define     pof             pop_front
#define     ins             insert
#define     vi              vector<int>
#define     pii             pair<int,int>
#define     mii             map<int,int>
#define     F               first
#define     S               second
#define     remax(a,b)      a=max(a,b)
#define     remin(a,b)      a=min(a,b)
#define     bitcount(x)     __builtin_popcountll(x)
#define     iceil(n,x)      (((n)-1)/(x)+1)
#define     db1(x)          cout<<#x<<"="<<x<<'\n'
#define     db2(x,y)        cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define     db3(x,y,z)      cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define     fo(i,n)         for(int i=0;i<(n);++i)
#define     dbvec(a)      cout<<#a<<": "; for(auto i:a) cout<<i<<" "; cout<<"\n"
#define     dbpairvec(a)  cout<<#a<<": \n"; for(auto i:a) cout<<i.F<<" "<<i.S<<"\n"
#define     readvec(a,n)    fo(i,n){int x;cin>>x;a.pb(x);}

using ull = unsigned long long;
using ll = long long;
using ld = long double;

const ld pi = acos(-1);
const ll inf = 1e18, mod = 1e9 + 7;
const ll N = 2e5 + 100;
const string alphabet = "abcdefghijklmnopqrstuvwxyz";
void test_case()
{
	int a; cin >> a;
	int b = a;
	while (b >= 10) {
		b = 0;
		while (a > 0) {
			b += a % 10; a = a / 10;
		}
		a = b;
	}
	cout << b << endl;
}
int32_t main() {
	fast();
	ll tt = 1;
	//cin >> tt;
	while (tt--) {
		test_case();
	}
	return 0;
}
### Prompt

Your task is to create a Cpp solution to 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
//CF: Ankit Singh

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

#define     prec(n)         fixed<<setprecision(n)
#define     int             long long int
#define     fast()          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)          begin(x),end(x)
#define     rz(x)           resize(x)
#define     asn(x,y)        assign(x,y)
#define     mem(a,b)        memset(a,b,sizeof(a))
#define     sz(x)           ((int)size(x))
#define     eb              emplace_back
#define     pb              push_back
#define     pf              push_front
#define     pob             pop_back
#define     pof             pop_front
#define     ins             insert
#define     vi              vector<int>
#define     pii             pair<int,int>
#define     mii             map<int,int>
#define     F               first
#define     S               second
#define     remax(a,b)      a=max(a,b)
#define     remin(a,b)      a=min(a,b)
#define     bitcount(x)     __builtin_popcountll(x)
#define     iceil(n,x)      (((n)-1)/(x)+1)
#define     db1(x)          cout<<#x<<"="<<x<<'\n'
#define     db2(x,y)        cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define     db3(x,y,z)      cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define     fo(i,n)         for(int i=0;i<(n);++i)
#define     dbvec(a)      cout<<#a<<": "; for(auto i:a) cout<<i<<" "; cout<<"\n"
#define     dbpairvec(a)  cout<<#a<<": \n"; for(auto i:a) cout<<i.F<<" "<<i.S<<"\n"
#define     readvec(a,n)    fo(i,n){int x;cin>>x;a.pb(x);}

using ull = unsigned long long;
using ll = long long;
using ld = long double;

const ld pi = acos(-1);
const ll inf = 1e18, mod = 1e9 + 7;
const ll N = 2e5 + 100;
const string alphabet = "abcdefghijklmnopqrstuvwxyz";
void test_case()
{
	int a; cin >> a;
	int b = a;
	while (b >= 10) {
		b = 0;
		while (a > 0) {
			b += a % 10; a = a / 10;
		}
		a = b;
	}
	cout << b << endl;
}
int32_t main() {
	fast();
	ll tt = 1;
	//cin >> tt;
	while (tt--) {
		test_case();
	}
	return 0;
}
```