Complement to 0 - advanced

We can reduce any number to 0 by repeatedly applying a complement operation to it in its binary form:
5 = 101 β†’ 10 β†’ 1 β†’ 0 β‡’ 3 complement operations.
This time you’re asked to calculate the number of operations required to get to 0 for really large bit-strings.

Input

The input contains a single line representing the bit-string s (1 ≀ |s| ≀ ).

Output

The output should contain a single integer - the number of complement operations we need to perform to turn s into 0.

Examples

Input
Output
111111000111110011100
6

Explanation

111111000111110011100 β†’ 111000001100011 β†’ 111110011100 β†’ 1100011 β†’ 11100 β†’ 11 β†’ 0
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue