
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <numeric>
#include <vector>
#include <string>
#include <cmath>
#include <list>
#include <set>
#include <map>

using namespace std;

#define ZERO_INDEXED 0

#define FORR(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)
#define FOR(i, a) FORR(i, !ZERO_INDEXED, a - ZERO_INDEXED)
#define FORRI(a, b) FORR(i, a, b)
#define FORI(a) FOR(i, a)
#define FORIN FORI(N)

#define RROF(i, a, b) for (int i = (int)(a); i >= (int)(b); i--)
#define ROF(i, a) RROF(i, a - ZERO_INDEXED, !ZERO_INDEXED)
#define RROFI(a, b) RROF(i, a, b)
#define ROFI(a) ROF(i, a)
#define ROFIN ROFI(N)

#define FORT(it, l) for (auto it = (l).begin(); it != (l).end();)
#define FORIT(l) FORT(it, l)

#define FORA(e, l) for (auto e : l)
#define FORE(l) FORA(e, l)

#define SIN cin
#define RN SIN >> N
#define RNM RN >> M
#define RNK RN >> K
#define RNMK RNM >> K
#define RARR(A, N) FORI(N) SIN >> A[i]
#define RARR2(A, N) RARR(A, N)[0] >> A[i][1]
#define RARR3(A, N) RARR2(A, N) >> A[i][2]
#define RARR0(A, N) FORRI(0, N - 1) SIN >> A[i]
#define RA RARR(A, N)
#define RA2 RARR2(A, N)
#define RA3 RARR3(A, N)
#define RA0 RARR0(A, N)
#define RNA RN; RA
#define RNA2 RN; RA2
#define RNA3 RN; RA3
#define RDADJ FORI(M) SIN >> u >> v, adj[u].insert(v)
#define RUADJ RDADJ, adj[v].insert(u)

#define CLEAR(x) memset(x, 0, sizeof(x))
#define FILL(x) memset(x, ~(char)0, sizeof(x))
#define SRT(l) sort(l.begin(), l.end())
#define SRTC(l, c) sort(l.begin(), l.end(), c)
#define SRTN(l) sort(l + 1, l + N + 1)
#define SRTNC(l, c) sort(l + 1, l + N + 1, c)
#define REV(l) reverse(l.begin(), l.end())
#define REVN(l) reverse(l + 1, l + N + 1)

#define SUM(l) accumulate(l.begin(), l.end(), 0)
#define SUMA(a, n) accumulate(a, a + n, 0)
#define SUMN(a) SUMA(a + 1, N)

#define MOD(x) (MOD_VAL + (x) % MOD_VAL) % MOD_VAL
#define MULT(x, y) MOD((lli)(x) * (lli)(y))
#define ADD(x, y) MOD((lli)(x) + (lli)(y))
#define INV(x) exp((x), MOD_VAL - 2)
#define MMULT(x, y) x = MULT(x, y)
#define MADD(x, y) x = ADD(x, y)
#define MOD_VAL 1000000007LL

#define NCHK(n, k) ((k) < 0 || (k) > (n) ? 0 : MULT(fac[n], MULT(ifac[k], ifac[(n) - (k)])))

#define MGET(m, k) [&](){ auto it = (m).find(k); return it == (m).end() ? 0 : it->se; }()
#define MINC(m, k, v) [&](){ auto it = (m).find(k); if (it == (m).end()) (m).insert({ (k), (v) }); else it->se += (v); }()

#define fi first
#define se second

#define CHNL out[out.length() - 1] = '\n'
#define OUTN(x) out += TOS(x), APNL
#define OUTS(x) out += TOS(x) + " "
#define OUTA(l) FORA(e, l) OUTS(e); CHNL
#define OUTF(a, n) FOR(i, n) OUTS((a)[i]); CHNL
#define APNL out += "\n"
#define TOS(x) to_string(x)

#define FAIL { out += "-1\n"; return; }

#define MAX_N 500000
#define NBT 32

typedef long double ld;
typedef unsigned int ui;
typedef long long int lli;
typedef pair<int, int> pii;
typedef pair<lli, lli> pll;
typedef set<int, bool(*)(int, int)> sic;
typedef set<pii, bool(*)(pii, pii)> spic;
typedef set<lli, bool(*)(lli, lli)> slc;
typedef set<pll, bool(*)(pll, pll)> splc;
typedef unordered_map<string, int> umsi;
typedef unordered_map<int, int> umii;
typedef unordered_map<lli, lli> umll;
typedef unordered_set<int> usi;
typedef unordered_set<lli> usl;
typedef map<string, int> msi;
typedef map<int, int> mii;
typedef map<lli, lli> mll;
typedef vector<int> vi;
typedef vector<lli> vl;
typedef list<pii> lpi;
typedef list<pll> lpl;
typedef list<int> li;
typedef list<lli> ll;
typedef set<pii> spi;
typedef set<pll> spl;
typedef set<int> si;
typedef set<lli> sl;
typedef string str;

pii operator+(const pii& x, const pii& y) { return { x.fi + y.fi, x.se + y.se }; }
pll operator+(const pll& x, const pll& y) { return { x.fi + y.fi, x.se + y.se }; }

lli gcd(lli a, lli b) { return a >= b ? b ? gcd(b, a % b) : a : gcd(b, a); }
lli lcm(lli a, lli b) { return a / gcd(a, b) * b; }

lli exp(lli a, lli b)
{
	lli r = 1;
	while (b) MMULT(r, b & 1 ? a : 1), MMULT(a, a), b >>= 1;
	return r;
}

lli fac[MAX_N];
lli ifac[MAX_N];

void mkfac()
{
	fac[0] = ifac[0] = 1;
	FORI(MAX_N - 1) fac[i] = MULT(fac[i - 1], i), ifac[i] = INV(fac[i]);
}

str out;
lli T;

usi adj[MAX_N];
int A[MAX_N];
int N, M, K;
int u, v;
str S;

void process() {}

int main()
{
	//mkfac();
	ios_base::sync_with_stdio(false);
	RN;
	while(N > 9) {
		int i = 0;
		FORE(TOS(N)) i += e - '0';
		N = i;
	}
	cout << N << endl;
	return 0;
}

### Prompt

In CPP, your task is to solve 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 <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <numeric>
#include <vector>
#include <string>
#include <cmath>
#include <list>
#include <set>
#include <map>

using namespace std;

#define ZERO_INDEXED 0

#define FORR(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)
#define FOR(i, a) FORR(i, !ZERO_INDEXED, a - ZERO_INDEXED)
#define FORRI(a, b) FORR(i, a, b)
#define FORI(a) FOR(i, a)
#define FORIN FORI(N)

#define RROF(i, a, b) for (int i = (int)(a); i >= (int)(b); i--)
#define ROF(i, a) RROF(i, a - ZERO_INDEXED, !ZERO_INDEXED)
#define RROFI(a, b) RROF(i, a, b)
#define ROFI(a) ROF(i, a)
#define ROFIN ROFI(N)

#define FORT(it, l) for (auto it = (l).begin(); it != (l).end();)
#define FORIT(l) FORT(it, l)

#define FORA(e, l) for (auto e : l)
#define FORE(l) FORA(e, l)

#define SIN cin
#define RN SIN >> N
#define RNM RN >> M
#define RNK RN >> K
#define RNMK RNM >> K
#define RARR(A, N) FORI(N) SIN >> A[i]
#define RARR2(A, N) RARR(A, N)[0] >> A[i][1]
#define RARR3(A, N) RARR2(A, N) >> A[i][2]
#define RARR0(A, N) FORRI(0, N - 1) SIN >> A[i]
#define RA RARR(A, N)
#define RA2 RARR2(A, N)
#define RA3 RARR3(A, N)
#define RA0 RARR0(A, N)
#define RNA RN; RA
#define RNA2 RN; RA2
#define RNA3 RN; RA3
#define RDADJ FORI(M) SIN >> u >> v, adj[u].insert(v)
#define RUADJ RDADJ, adj[v].insert(u)

#define CLEAR(x) memset(x, 0, sizeof(x))
#define FILL(x) memset(x, ~(char)0, sizeof(x))
#define SRT(l) sort(l.begin(), l.end())
#define SRTC(l, c) sort(l.begin(), l.end(), c)
#define SRTN(l) sort(l + 1, l + N + 1)
#define SRTNC(l, c) sort(l + 1, l + N + 1, c)
#define REV(l) reverse(l.begin(), l.end())
#define REVN(l) reverse(l + 1, l + N + 1)

#define SUM(l) accumulate(l.begin(), l.end(), 0)
#define SUMA(a, n) accumulate(a, a + n, 0)
#define SUMN(a) SUMA(a + 1, N)

#define MOD(x) (MOD_VAL + (x) % MOD_VAL) % MOD_VAL
#define MULT(x, y) MOD((lli)(x) * (lli)(y))
#define ADD(x, y) MOD((lli)(x) + (lli)(y))
#define INV(x) exp((x), MOD_VAL - 2)
#define MMULT(x, y) x = MULT(x, y)
#define MADD(x, y) x = ADD(x, y)
#define MOD_VAL 1000000007LL

#define NCHK(n, k) ((k) < 0 || (k) > (n) ? 0 : MULT(fac[n], MULT(ifac[k], ifac[(n) - (k)])))

#define MGET(m, k) [&](){ auto it = (m).find(k); return it == (m).end() ? 0 : it->se; }()
#define MINC(m, k, v) [&](){ auto it = (m).find(k); if (it == (m).end()) (m).insert({ (k), (v) }); else it->se += (v); }()

#define fi first
#define se second

#define CHNL out[out.length() - 1] = '\n'
#define OUTN(x) out += TOS(x), APNL
#define OUTS(x) out += TOS(x) + " "
#define OUTA(l) FORA(e, l) OUTS(e); CHNL
#define OUTF(a, n) FOR(i, n) OUTS((a)[i]); CHNL
#define APNL out += "\n"
#define TOS(x) to_string(x)

#define FAIL { out += "-1\n"; return; }

#define MAX_N 500000
#define NBT 32

typedef long double ld;
typedef unsigned int ui;
typedef long long int lli;
typedef pair<int, int> pii;
typedef pair<lli, lli> pll;
typedef set<int, bool(*)(int, int)> sic;
typedef set<pii, bool(*)(pii, pii)> spic;
typedef set<lli, bool(*)(lli, lli)> slc;
typedef set<pll, bool(*)(pll, pll)> splc;
typedef unordered_map<string, int> umsi;
typedef unordered_map<int, int> umii;
typedef unordered_map<lli, lli> umll;
typedef unordered_set<int> usi;
typedef unordered_set<lli> usl;
typedef map<string, int> msi;
typedef map<int, int> mii;
typedef map<lli, lli> mll;
typedef vector<int> vi;
typedef vector<lli> vl;
typedef list<pii> lpi;
typedef list<pll> lpl;
typedef list<int> li;
typedef list<lli> ll;
typedef set<pii> spi;
typedef set<pll> spl;
typedef set<int> si;
typedef set<lli> sl;
typedef string str;

pii operator+(const pii& x, const pii& y) { return { x.fi + y.fi, x.se + y.se }; }
pll operator+(const pll& x, const pll& y) { return { x.fi + y.fi, x.se + y.se }; }

lli gcd(lli a, lli b) { return a >= b ? b ? gcd(b, a % b) : a : gcd(b, a); }
lli lcm(lli a, lli b) { return a / gcd(a, b) * b; }

lli exp(lli a, lli b)
{
	lli r = 1;
	while (b) MMULT(r, b & 1 ? a : 1), MMULT(a, a), b >>= 1;
	return r;
}

lli fac[MAX_N];
lli ifac[MAX_N];

void mkfac()
{
	fac[0] = ifac[0] = 1;
	FORI(MAX_N - 1) fac[i] = MULT(fac[i - 1], i), ifac[i] = INV(fac[i]);
}

str out;
lli T;

usi adj[MAX_N];
int A[MAX_N];
int N, M, K;
int u, v;
str S;

void process() {}

int main()
{
	//mkfac();
	ios_base::sync_with_stdio(false);
	RN;
	while(N > 9) {
		int i = 0;
		FORE(TOS(N)) i += e - '0';
		N = i;
	}
	cout << N << endl;
	return 0;
}

```