2181: 数根

题目描述

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

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

输入格式

单个整数，表示输入的数字 n。

输出格式

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

数据范围

对于 40% 的数据，1≤n<2³¹；

对于 80% 的数据，1≤n<2⁶³；

对于 100% 的数据，1≤n<10¹⁰⁰⁰。

样例数据

输入:

123

输出:

6

输入:

999

输出:

9

输入:

314159265358979323846264338328

输出:

7