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 shuru int t;cin>>t;while(t--)
#define F for(int i=0;i<n;i++)

int findsum(int a){
    int sum=0,rem=0;
    while(a>0){
        rem=a%10;
        sum+=rem;
        a=a/10;
    }
    if(sum>=10) {return findsum(sum);}
    else {
    return sum;}
}

int  main(){
    int a;cin>>a;
    int res=findsum(a);
    cout<<res<<endl;
}