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>

using namespace std;
#define int long long int
#define mod 1000000007

int sod(int a)
{
   int ans=0;
   while(a>0)
   {
      ans+=(a%10);
      a/=10;
   }
   return ans;
}
void solve()
{ 
   int x; cin>>x;
   while(x>=10)
   {
     x= sod(x);
   }
   cout<<x;
}

signed main()
{
   int t;
   t=1;
    //cin>>t;
   while(t--)
   {
       solve();
   } 
   return 0;
}