Increasing Numbers

We will call a non-negative integer increasing if, for any two adjacent digits in its decimal representation, the digit to the right is greater than or equal to the digit to the left. For example, 1558, 11, 3 and 0 are all increasing; 10 and 20170312 are not.

Snuke has an integer N. Find the minimum number of increasing integers that can represent N as their sum.

Constraints

• 1 \leq N \leq 10^{500000}

Input

The input is given from Standard Input in the following format:

N

Output

Print the minimum number of increasing integers that can represent N as their sum.

Examples

Input

80

Output

2

Input

123456789

Output

1

Input

20170312

Output

4

Input

7204647845201772120166980358816078279571541735614841625060678056933503

Output

31

inputFormat

Input

The input is given from Standard Input in the following format:

N

outputFormat

Output

Print the minimum number of increasing integers that can represent N as their sum.

Examples

Input

80

Output

2

Input

123456789

Output

1

Input

20170312

Output

4

Input

7204647845201772120166980358816078279571541735614841625060678056933503

Output

31

样例

123456789

1