题目描述

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

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

输入格式

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

输出格式

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

样例

123

6

999

9

314159265358979323846264338328

7

数据范围/约定

• 对于 $40\%$ 的测试数据满足：$1≤n<2^{31}$。
• 对于 $80\%$ 的测试数据满足：$1≤n<2^{63}$。
• 对于 $100\%$ 的测试数据满足：$1≤n<10^{1000}$。