数根

问题描述

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

例如，456 的数根为 6，因为 $4+5+6=15$，继续分解得 $1+5=6$。给定 $n$，请输出它的数根。注意，有一部分 $n$ 非常大。

输入格式

单个整数，表示数字 $n$。

输出格式

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

样例输入 1

99999999999

样例输出 1

9

样例输入 2

314159265358979323846264338328

样例输出 2

7

样例解释

样例 1 解释 样例 1 的数根计算过程如下：$99999999999 \Rightarrow 99 \Rightarrow 18 \Rightarrow 9$。

数据范围与约定

• 对于 40% 的数据，$1 \le n < 2^{31}$。
• 对于 80% 的数据，$1 \le n < 2^{63}$。
• 对于 100% 的数据，$1 \le n < 10^{1000}$。