#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll const MOD =1e9+7;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define endl "\n"
bool sortcol( const vector<int>& v1,
               const vector<int>& v2 ) {
 return v1[0] > v2[0];
}
void printArray(ll a[],ll n)
{
for(int i =0;i<n;i++)
cout<<a[i]<<" ";
cout<<"\n";
}
bool sortbysec(const pair<int,int> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
}

void printVec(vector<ll> v)
{
int s = v.size();
for(int i =0;i<s;i++)
cout<<v[i]<<" ";
cout<<"\n";
}
void printBool(bool b)
{
  if(b) cout<<"YES\n";
  else cout<<"NO\n";
}
ll mod(ll n)
{
    if(n>=0)
        return n;
    else return -1*n;
}
void swapp(ll&a,ll&b)
{
    ll temp = a;
    a=b;
    b=temp;
}
string func(string s)
{
    ll sum =0;
    for(int i =0;i<s.length();i++)
    {
        sum+=s[i]-'0';
    }
    string a=to_string(sum);
    return a;
}
int main()
{  // ios_base::sync_with_stdio(false);
    //cin.tie(NULL);

   {
    string s ;cin>>s;
    ll sum=0;

   while(s.length()>1)
   {
       s = func(s);
   }
    cout<<s<<endl;


}
}

### Prompt

Construct a CPP code solution to the problem outlined:

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<bits/stdc++.h>
using namespace std;
#define ll long long int
ll const MOD =1e9+7;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define endl "\n"
bool sortcol( const vector<int>& v1,
               const vector<int>& v2 ) {
 return v1[0] > v2[0];
}
void printArray(ll a[],ll n)
{
for(int i =0;i<n;i++)
cout<<a[i]<<" ";
cout<<"\n";
}
bool sortbysec(const pair<int,int> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
}

void printVec(vector<ll> v)
{
int s = v.size();
for(int i =0;i<s;i++)
cout<<v[i]<<" ";
cout<<"\n";
}
void printBool(bool b)
{
  if(b) cout<<"YES\n";
  else cout<<"NO\n";
}
ll mod(ll n)
{
    if(n>=0)
        return n;
    else return -1*n;
}
void swapp(ll&a,ll&b)
{
    ll temp = a;
    a=b;
    b=temp;
}
string func(string s)
{
    ll sum =0;
    for(int i =0;i<s.length();i++)
    {
        sum+=s[i]-'0';
    }
    string a=to_string(sum);
    return a;
}
int main()
{  // ios_base::sync_with_stdio(false);
    //cin.tie(NULL);

   {
    string s ;cin>>s;
    ll sum=0;

   while(s.length()>1)
   {
       s = func(s);
   }
    cout<<s<<endl;


}
}

```