// Problem: B. DMCA
// Contest: Codeforces - April Fools Day Contest 2021
// URL: https://codeforces.com/contest/1505/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 2e5 + 10;

int calc(int n) {
  int ret = 0;
  while (n) {
    ret += n % 10;
    n /= 10;
  }
  return ret;
}

void solve() {
  int n;
  cin >> n;
  while (n >= 10) {
    n = calc(n);
  }
  cout << n;
}

int main() {
  // ios_base::sync_with_stdio(false);
  int T = 1;
  // scanf("%d", &T);
  while (T--) {
    solve();
  }
  return 0;
}
### 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
// Problem: B. DMCA
// Contest: Codeforces - April Fools Day Contest 2021
// URL: https://codeforces.com/contest/1505/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 2e5 + 10;

int calc(int n) {
  int ret = 0;
  while (n) {
    ret += n % 10;
    n /= 10;
  }
  return ret;
}

void solve() {
  int n;
  cin >> n;
  while (n >= 10) {
    n = calc(n);
  }
  cout << n;
}

int main() {
  // ios_base::sync_with_stdio(false);
  int T = 1;
  // scanf("%d", &T);
  while (T--) {
    solve();
  }
  return 0;
}
```