#include <bits/stdc++.h>
#include <cmath>

#define  fl(i,a,b) for(long long i=a;i<b;i++)
#define  test long long t_c;cin>>t_c;for(long long ks=1;ks<=t_c;ks++)
#define pb push_back
#define vi vector<int>
#define all(x) x.begin(),x.end()
#define cy cout<<"YES\n";
#define cn cout<<"NO\n";

#define case(x) cout<<"Case "<<x<<": ";



typedef long long ll;
typedef long long int lli;
void sc(int &x){scanf("%d",&x);}
void sc(lli &x){scanf("%lld",&x);}
void sc(char *x){scanf("%s",x);}
void sc(double &x){scanf("%lf",&x);}

using namespace std;
lli sum(lli a)
{
    lli n=0;
    while(a)
    {
        n+=(a%10);
        a/=10;
    }
    return n;
}
int main()
{
      ios_base::sync_with_stdio(false);

          lli a;
          cin>>a;
          while(a>=10)
          {
              a=sum(a);
          }
          cout<<a<<endl;


}

### 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 <bits/stdc++.h>
#include <cmath>

#define  fl(i,a,b) for(long long i=a;i<b;i++)
#define  test long long t_c;cin>>t_c;for(long long ks=1;ks<=t_c;ks++)
#define pb push_back
#define vi vector<int>
#define all(x) x.begin(),x.end()
#define cy cout<<"YES\n";
#define cn cout<<"NO\n";

#define case(x) cout<<"Case "<<x<<": ";



typedef long long ll;
typedef long long int lli;
void sc(int &x){scanf("%d",&x);}
void sc(lli &x){scanf("%lld",&x);}
void sc(char *x){scanf("%s",x);}
void sc(double &x){scanf("%lf",&x);}

using namespace std;
lli sum(lli a)
{
    lli n=0;
    while(a)
    {
        n+=(a%10);
        a/=10;
    }
    return n;
}
int main()
{
      ios_base::sync_with_stdio(false);

          lli a;
          cin>>a;
          while(a>=10)
          {
              a=sum(a);
          }
          cout<<a<<endl;


}

```