#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double lld;

#define fo(n)   for(int i=0;i<n;i++)
#define rep(i,x,n)   for(auto i=x;i<n;i++)
#define pb      push_back
#define ppb     pop_back
#define mem0(a) memset(a,0,sizeof(a))
#define all(v)  v.begin(),v.end()
#define ch " "
#define nline "\n"
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);

const int MOD=1e9+7;
const int INF=1e9+20;
const ll INFLL=2e18;
const int MAX=1e5+20;

// bool comp(int i,int j){
//     return i<=j;        //last minimum fn comparator
// }

// bool comp(pair<int,int>&a,pair<int,int>&b){
//     if(a.first!=b.first)    return a.first>b.first;
//     return a.first<a.second;
// }

// bool pow2(int x){
//     return x && (!(x&(x-1)));
// }

void solve(){
    ll n;
    cin >> n;
    while(n/10 != 0){
        int val = 0;
        while(n){
            val += (n%10);
            n/=10;
        }
        n = val;
    }
    cout<<n<<nline;
}   

int main(){
    fastio;

    auto start=chrono::high_resolution_clock::now();

    // freopen("input.in","r",stdin);   
    // freopen("output.out","w",stdout);

    int t=1;
    // cin>>t;
    for(int i=1;i<=t;i++){
        // cout<<"Case #"<<i<<": ";
        solve();
    }

    auto end=chrono::high_resolution_clock::now();
    double time_taken=chrono::duration_cast<chrono::nanoseconds>(end-start).count();
    time_taken*=1e-9;
    // cerr<<"time taken: "<<fixed<<time_taken<<setprecision(9)<<endl;   
}

### Prompt

Generate 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 <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double lld;

#define fo(n)   for(int i=0;i<n;i++)
#define rep(i,x,n)   for(auto i=x;i<n;i++)
#define pb      push_back
#define ppb     pop_back
#define mem0(a) memset(a,0,sizeof(a))
#define all(v)  v.begin(),v.end()
#define ch " "
#define nline "\n"
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);

const int MOD=1e9+7;
const int INF=1e9+20;
const ll INFLL=2e18;
const int MAX=1e5+20;

// bool comp(int i,int j){
//     return i<=j;        //last minimum fn comparator
// }

// bool comp(pair<int,int>&a,pair<int,int>&b){
//     if(a.first!=b.first)    return a.first>b.first;
//     return a.first<a.second;
// }

// bool pow2(int x){
//     return x && (!(x&(x-1)));
// }

void solve(){
    ll n;
    cin >> n;
    while(n/10 != 0){
        int val = 0;
        while(n){
            val += (n%10);
            n/=10;
        }
        n = val;
    }
    cout<<n<<nline;
}   

int main(){
    fastio;

    auto start=chrono::high_resolution_clock::now();

    // freopen("input.in","r",stdin);   
    // freopen("output.out","w",stdout);

    int t=1;
    // cin>>t;
    for(int i=1;i<=t;i++){
        // cout<<"Case #"<<i<<": ";
        solve();
    }

    auto end=chrono::high_resolution_clock::now();
    double time_taken=chrono::duration_cast<chrono::nanoseconds>(end-start).count();
    time_taken*=1e-9;
    // cerr<<"time taken: "<<fixed<<time_taken<<setprecision(9)<<endl;   
}

```