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 <bits/stdc++.h>
#include<unordered_map>
//#pragma GCC optimize(2)
#define ll long long
#define sc(n) scanf("%d",&n)
#define scl(n) scanf("%lld",&n)
//#define int ll
using namespace std;
inline int rd() { int x = 0, f = 1; char c = getchar(); while (c != '-' && c < 48)c = getchar(); if (c == '-')f = -1, c = getchar(); while (c > 47)x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return f * x; }
const int maxn = 500001, inf = 2147483647;
const ll mod = 1 ? 998244353 : 1000000007, linf = 9223372036854775807;
const double pi = acos(-1);
inline ll mi(ll a, ll b, ll mm = mod) { a %= mm; ll u = 1; while (b) { if (b & 1)u = u * a % mm; a = a * a % mm, b >>= 1; }return u; }
inline ll gcd(ll a, ll b) { ll c = a % b; while (c)a = b, b = c, c = a % b; return b; }
inline void mem(int* a, int p = 0, int len = maxn) { for (int i = 0; i < len; i++)a[i] = p; }
struct p { int x, n; }e[maxn];
static bool cmp(p i, p j) { return i.x < j.x; };
int t, n, m, a[maxn], b[maxn], c[maxn], d[maxn], x, y, xx, yy, su, q, k, u, l, r;
unordered_map<int, int>ma;
string s = "NO";
signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);//sf和cin混用会出错
	cin >> n;
	while (n > 9) {
		su = 0;
		while (n)
			su += n % 10, n /= 10;
		n = su;
	}
	cout << n;
}