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 <algorithm>
#include <iostream>
#include <cstring>
#include <ctime>

#define end cout<<endl
#define lo long long 
int size;
#define forx for(int i=0;i<size;i++)
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int main () 
{
	fast
	cin>>size;
	size=size%9;
	if(size==0)
	size=9;
	cout<<size;
	
}