数根

题目描述

给定一个正整数n，若n在十进制下的各位数字之和小于10，则这个和是n的数根。否则，继续求这个和在十进制下的各位数字之和，直到结果小于10为止，定义最后的结果为n的数根。

例如，999的数根为9，因为9+9+9=27，继续分解得2+7=9。给定n，请输出它的数根。注意，有一部分n非常大。

输入描述

单个整数，表示数字n。

输出描述

单个整数：表示n的数根。

数据范围

• 对于40%的数据，1≤n<10^31；
• 对于80%的数据，1≤n<10^63；
• 对于100%的数据，1≤n<10^1000。