BINSTR - Binary Strings

no tags 

Mahesh loves to play around with Binary Strings. He defines binary strings as a string made of only '0' and '1' (possibly empty). After years of research on binary string,
he found something known as Stable binary string. A stable binary string can be defined as :

1. An empty binary string is stable.
2. If B is stable, then "0+B+1" is also stable.
3. If A and B are two stable binary strings, then "A+B" is also stable.

(+ means concatenation here, quotes for clarity)

For example, "01", "0101", "0011", are stable binary strings while "10", "11", "00", "1001", etc are unstable ones. Mahesh found out that a lot of binary strings are unstable,
so he is in a mood to convert them to stable strings. He can do a single operation of changing a '1' to '0' or a '0' to '1' infintely many times. He wants you to convert a
given binary string into a stable binary string in minimum number of operations.


Input contains multiple lines of testcases. Each line contains a single string consisting of only '1' and '0' and the size of string is no more than 20000 and is of even size. Input terminates
by a single '-' in a single line.


For each line of input except the last one, output the test case number followed by a space followed by a single integer - the minimum no. of operations required to convert the given string to stable binary string.
See sample I/O for clarifications.





1. 2
2. 0
3. 1

Added by:Mahesh Chandra Sharma
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem