Let $\textrm{pop}(n)$ is number ones n have in binary. For example, $\textrm{pop}(11) = \textrm{pop}(1011_2) = 3.$

For integer d, define $f(d) = \min_{n \geqslant 0} \textrm{pop}(n \oplus (n + d)).$
Here $\oplus$ denotes binary XOR.
You are given d in binary, find $f(d)$.

Input Format:
Single line contains binary representation of d without leading zeroes.

Output Format:
One integer in decimal numeral system -- $f(d).$

Constraints:
$1 \leqslant d < 2 ^ {200,000}.$
50 points
$1 \leqslant d < 2 ^ {40}.$