#87. 土拨鼠可长可短的如意金箍棒

土拨鼠可长可短的如意金箍棒

Background

美鼠王文轩拥有一根别人非常羡慕的可长可短的如意金箍棒.

Description

这一天, 文轩又玩起了他的金箍棒, 他在想, 金箍棒最短可以是多短呢?

我们可以把金箍棒看作是一段一段组成的, 每一段上都有一个0到9的数字.

他想通过变换将金箍棒变短.

变换的方式为: 每一次将各个数字相加, 得到的和就是新的金箍棒状态.

文轩现在想知道, 金箍棒最短是多少?

Format

Input

一个整数n, 表示金箍棒最初的状态.

Output

一个整数, 表示最终金箍棒最短的长度.

Samples

样例1

19
1

样例解析

1+9 = 10, 1+0 = 1

样例2

998244353
2

Limitation

1n1010001 \le n \le 10^{1000}