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

#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define in insert
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define prec fixed << setprecision(20)
#define sz(v) (int)(v.size())
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mem(a, s) memset(a, s, sizeof(a))
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define repr(i, a, b) for (int i = a; i >= b; --i)
#define MAX 8000000000000000064LL
#define MIN -8000000000000000064LL
#define endl "\n"

typedef vector<int> vi;
typedef stack<int> sti;
typedef queue<int> qi;
typedef pair<int, int> pii;
typedef set<int> si;
typedef map<int, int> mii;
typedef vector<pii> vpi;
typedef priority_queue<int> pqmax;
typedef priority_queue<int, vector<int>, greater<int>> pqmin;

const int mod = 1e9 + 7;
const int inf = 1e18;
const int dx[8] = { -1, 0, 1, 0, -1, 1, 1, -1},
                  dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int kdx[8] = { -2, -1, 1, 2, 2, 1, -1, -2},
                   kdy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

void solve() {
    string s;
    cin >> s;
    do {
        int sum = 0;
        for (auto x : s) {
            sum += (x - '0');
        }
        s = to_string(sum);
    } while (sz(s) != 1);
    cout << s << endl;
}

int32_t main() {
    clock_t start = clock();
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t = 1;
    // cin >> t;
    rep(i, 1, t) {
        // cout << "Case #" << i << ": ";
        solve();
    }
    double duration = (clock() - start) / (double)CLOCKS_PER_SEC;
    cerr << duration << 's' << endl;
    return 0;
}
### 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 int long long
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define in insert
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define prec fixed << setprecision(20)
#define sz(v) (int)(v.size())
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mem(a, s) memset(a, s, sizeof(a))
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define repr(i, a, b) for (int i = a; i >= b; --i)
#define MAX 8000000000000000064LL
#define MIN -8000000000000000064LL
#define endl "\n"

typedef vector<int> vi;
typedef stack<int> sti;
typedef queue<int> qi;
typedef pair<int, int> pii;
typedef set<int> si;
typedef map<int, int> mii;
typedef vector<pii> vpi;
typedef priority_queue<int> pqmax;
typedef priority_queue<int, vector<int>, greater<int>> pqmin;

const int mod = 1e9 + 7;
const int inf = 1e18;
const int dx[8] = { -1, 0, 1, 0, -1, 1, 1, -1},
                  dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int kdx[8] = { -2, -1, 1, 2, 2, 1, -1, -2},
                   kdy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

void solve() {
    string s;
    cin >> s;
    do {
        int sum = 0;
        for (auto x : s) {
            sum += (x - '0');
        }
        s = to_string(sum);
    } while (sz(s) != 1);
    cout << s << endl;
}

int32_t main() {
    clock_t start = clock();
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t = 1;
    // cin >> t;
    rep(i, 1, t) {
        // cout << "Case #" << i << ": ";
        solve();
    }
    double duration = (clock() - start) / (double)CLOCKS_PER_SEC;
    cerr << duration << 's' << endl;
    return 0;
}
```