#include <iostream>

using namespace std;

int digroot(int k){
    if(k == 0) return 0;
    else return digroot(k / 10) + k % 10;
}

int main(){
    int k;
    cin >> k;
    while(k >= 10){
        k = digroot(k);
    }
    cout << k << 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 <iostream>

using namespace std;

int digroot(int k){
    if(k == 0) return 0;
    else return digroot(k / 10) + k % 10;
}

int main(){
    int k;
    cin >> k;
    while(k >= 10){
        k = digroot(k);
    }
    cout << k << endl;
    return 0;
}
```