#pragma region template
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <utility>
#include <set>
#include <string>
#include <queue>
#include <tuple>
using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<vector<pii>> vvpii;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define loop(i,x) for (ll i = 0;i<(x);(i)++)
#define loopr(i,x) for (ll i = (x);i>=0;(i)--)
const long long INF = 2e18, MOD = 1e9 + 7;
#pragma endregion
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	/*ll a,b; cin >> a >> b;
	if (a == 2 || a == 33) cout << "YES";
	else cout << "NO";*/
	/*if (a == 26 || a == 3) cout << "NO";
	else cout << "YES";*/
	string n; cin >> n;
	ll a = 0;
	for (auto b : n) {
		string s = "";
		s += b;
		a += stoi(s);
	}
	n = to_string(a);
	a = 0;
	for (auto b : n) {
		string s = "";
		s += b;
		a += stoi(s);
	}
	n = to_string(a);
	a = 0;
	for (auto b : n) {
		string s = "";
		s += b;
		a += stoi(s);
	}
	cout << a;
	return 0;
}
### Prompt

Your challenge is to write 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
#pragma region template
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <utility>
#include <set>
#include <string>
#include <queue>
#include <tuple>
using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<vector<pii>> vvpii;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define loop(i,x) for (ll i = 0;i<(x);(i)++)
#define loopr(i,x) for (ll i = (x);i>=0;(i)--)
const long long INF = 2e18, MOD = 1e9 + 7;
#pragma endregion
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	/*ll a,b; cin >> a >> b;
	if (a == 2 || a == 33) cout << "YES";
	else cout << "NO";*/
	/*if (a == 26 || a == 3) cout << "NO";
	else cout << "YES";*/
	string n; cin >> n;
	ll a = 0;
	for (auto b : n) {
		string s = "";
		s += b;
		a += stoi(s);
	}
	n = to_string(a);
	a = 0;
	for (auto b : n) {
		string s = "";
		s += b;
		a += stoi(s);
	}
	n = to_string(a);
	a = 0;
	for (auto b : n) {
		string s = "";
		s += b;
		a += stoi(s);
	}
	cout << a;
	return 0;
}
```