说明

对于一个整数，我们定义它的数位和为各个数位的和。比如$456789$的数位和为$4+5+6+7+8+9$也就是$39$。

我们对这个$a$不停地求数位和，直到它不超过$9$，把所有的中间结果输出。

比如$a=456789$，那么它的数位和是$39$。继续对$39$求数位和，得到$12$，继续对$12$操作，得到$3$。

输入格式

一个正整数$a$

输出格式

若干行，为$a$不停地求数位和，直到不超过$9$为止的所有结果

样例

456789

39
12
3

86471648912748124790174817001304807

149
14
5

数据范围

$50\%$的数据，$1\leq a\leq 10^9$

$80\%$的数据，$1\leq a\leq 10^{18}$

$100\%$的数据，$1\leq a\leq 10^{1000}$

提示

$10^9$在int范围内，$10^{18}$在long long范围内