## BINSTR - Binary Strings

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 SPECIFICATIONS**

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.**OUTPUT SPECIFICATIONS**

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.

SAMPLE I-O**INPUT**

10

010101

0001

-**OUTPUT**

1. 2

2. 0

3. 1

Added by: | Mahesh Chandra Sharma |

Date: | 2011-01-28 |

Time limit: | 0.242s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 |

Resource: | Own Problem |