#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdlib>

using namespace std;

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;

//typedef long long int i64; // 9e18
typedef long long int i64; // 9e18

typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

const long double PI = 3.141592653589793238463;
//const int MAXN = 1000500;
//const int MAXVALUE = 1000000500;
//const long double EPS = 1e-7;
const i64 INF = 1e18;
i64 mod = 1e9 + 7;
//i64 mod = 998244353;


i64 T, n, m, k;


//string s1;
//getline(cin, s1);



//bool comp(i64 a, i64 b)
//{
//    if (fr2[a] == fr2[b])
//        return (fr[a] < fr[b]);
//    return (fr2[a] < fr2[b]);
//
//}

i64 norm(i64 d, i64 MOD) {
    return ((d % MOD) + MOD) % MOD;
}

i64 add_m(i64 x, i64 y, i64 MOD) {
    return norm(norm(x, MOD) + norm(y, MOD), MOD);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(16);

    T = 1;
    //cin >> T;

    for (i64 tt = 1; tt <= T; ++tt) {

        i64 res = 0;
        cin >> n;

        while (true) {
            while (n) {
                res += n % 10;
                n /= 10;
            }
            if (res / 10 == 0) {
                break;
            }
            n = res;
            res = 0;
        }

        cout << res << endl;

        bool yes_no = false;
        if (yes_no) {
            bool fl = true;


            //fl ? cout << "Yes" << endl : cout << "No" << endl;

        }

    }


    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
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdlib>

using namespace std;

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;

//typedef long long int i64; // 9e18
typedef long long int i64; // 9e18

typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

const long double PI = 3.141592653589793238463;
//const int MAXN = 1000500;
//const int MAXVALUE = 1000000500;
//const long double EPS = 1e-7;
const i64 INF = 1e18;
i64 mod = 1e9 + 7;
//i64 mod = 998244353;


i64 T, n, m, k;


//string s1;
//getline(cin, s1);



//bool comp(i64 a, i64 b)
//{
//    if (fr2[a] == fr2[b])
//        return (fr[a] < fr[b]);
//    return (fr2[a] < fr2[b]);
//
//}

i64 norm(i64 d, i64 MOD) {
    return ((d % MOD) + MOD) % MOD;
}

i64 add_m(i64 x, i64 y, i64 MOD) {
    return norm(norm(x, MOD) + norm(y, MOD), MOD);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(16);

    T = 1;
    //cin >> T;

    for (i64 tt = 1; tt <= T; ++tt) {

        i64 res = 0;
        cin >> n;

        while (true) {
            while (n) {
                res += n % 10;
                n /= 10;
            }
            if (res / 10 == 0) {
                break;
            }
            n = res;
            res = 0;
        }

        cout << res << endl;

        bool yes_no = false;
        if (yes_no) {
            bool fl = true;


            //fl ? cout << "Yes" << endl : cout << "No" << endl;

        }

    }


    return 0;
}
```