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

Solution (in CPP):

Solution:

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <vector>
#include <string>
using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a-1);i>=(b);--i)
#define _TESTLOOP_ int T;cin>>T;while(T--)
typedef long long ll;
typedef long double ld;

string s;

string itos(int x) {
    string res;
    while (x) {
        res.push_back(x % 10 + '0');
        x /= 10;
    }
    return res;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin >> s;
    while (s.length() != 1) {
        int t = 0;
        rep(i, 0, s.length()) {
            t += s[i] - '0';
        }
        s = itos(t);
    }
    cout << s << endl;
    return 0;
}