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}.\)