说明

这道题比较难，我赌你 5秒内AC不了

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

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

输入格式

单个整数， 表示数字 n。

输出格式

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

样例

456

6

提示

输入

99999999999

输出

9

说明

【样例 1 解释】

样例 2 的数根计算过程如下： 99999999999 => 99 => 18 => 9

【数据范围】

对于 40% 的数据，$1 ≤ n≤ 2^{31}$

对于 80% 的数据，$1 ≤ n < 2^{63}$。

对于 100% 的数据，$1 ≤ n < 10^{1000}$。