I. Cyclic Apple Strings
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Leading the Fluttershies, we arrived at the Sweet Apple Acres.

"Only to see her lower her body, two front hooves pressed against the ground, waist twisted, legs kicked, two powerful hind legs striking the trunk like bullets. With a muffled sound accompanied by the rustling of leaves, the entire tree's apples fell into the basket without missing a beat," whispered one of the Fluttershies.

"Fluttershy, how do you have so many?" Would I talk like that, I had only just risen to this doubt when I was interrupted by Applejack's voice coming from far away.

"There's nothing wrong with that," another Fluttershy said coolly, as the apples in Applejack's basket inexplicably flew up one by one.

Strange, why would some of me even have magic? I hurriedly helped Applejack gather the apples and stopped the actions of Fluttershies.

Formally, the act of stopping can be abstracted into the following problem:

Given a string $$$s$$$ of length $$$n$$$ consisting only of 0 and 1. I can perform the following operation any number of times: choose a substring of $$$s$$$ and a positive number $$$k$$$, then cyclically shift the substring $$$k$$$ positions to the left.

String $$$a$$$ is a substring of string $$$b$$$ if and only if $$$a$$$ can be obtained by deleting some characters from the beginning and end of $$$b$$$ (which can be none or all of them).

Assume there is a string $$$s=s_0s_1s_2\dots s_{m-2}s_{m-1}$$$, shifting it $$$k$$$ positions to the left will result in $$$s_{k'}s_{k'+1}\dots s_{m-1}s_{0}s_{1}\dots s_{k'-2}s_{k'-1}$$$, where $$$k'=k\bmod m$$$.

A string $$$s$$$ consisting only of 0 and 1 is sorted if and only if for all $$$1 \leq i \lt n$$$, $$$s_i \leq s_{i+1}$$$. Here, characters are compared based on their numerical values.

For example, shifting the substring 1011 of string 0101100 two positions to the left results in 0111000.

I need to find the minimum number of operations required to make $$$s$$$ sorted.

Input

One line containing a string $$$s$$$ consisting only of 0 and 1, where $$$|s|$$$ denotes the length of $$$s$$$ ($$$1 \leq |s| \leq 10^5$$$).

Output

Output one line containing an integer, representing the minimum number of operations required to make $$$s$$$ sorted.

Examples
Input
01010101
Output
3
Input
11001010001
Output
3
Note

In the first example, one feasible set of minimal operations is 01010101 $$$\rightarrow$$$ 00110101 $$$\rightarrow$$$ 00011101 $$$\rightarrow$$$ 00001111, where we shift the substring $$$[1,2]$$$ by $$$1$$$ position, the substring $$$[2,4]$$$ by $$$2$$$ positions, and the substring $$$[3,6]$$$ by $$$3$$$ positions. Please note that string indices start from $$$0$$$.

In the second example, one feasible set of minimal operations is 1100101001 $$$\rightarrow$$$ 0011101001 $$$\rightarrow$$$ 0011100011 $$$\rightarrow$$$ 0000011111, where we shift the substring $$$[0,3]$$$ by $$$2$$$ positions, the substring $$$[6,8]$$$ by $$$1$$$ position, and the substring $$$[2,7]$$$ by $$$3$$$ positions.