Four year old Suzie was ecstatic to receive a large set of magnetic 0s and 1s for Christmas. She now spends most of her time using the letters to write out binary numbers on the kitchen fridge. Her most recent challenge has been to write out a number and then write it in reverse.

However, being a four year old, Suzie does not have a long reach. The only way she is able to change the number is to swap two adjacent bits. As an aspiring programmer and lazy child, she would like to make as few swaps as possible in order to reverse the number. Can you help Suzie figure out the fewest number of swaps she'll need to make?

Input

Each test case contains one number written in binary.

For ~40\%~ of the cases, the length of the number will not exceed ~100~.

For the remaining cases, the length of the number will not exceed ~100~ ~000~.

Output

Output the minimum number of swaps that Suzie has to make to reverse the number.

Sample Input

10110

Sample Output

2

Sample Input

101100010110010

Sample Output

10

Explanation for Sample Output

In the first case, Suzie only needs to swap the first and second bit, obtaining ~01110~, and then the last two bits, obtaining ~01101~.