Minimum Operations to Make a Binary String Uniform

Given a binary string, you are allowed to perform an operation that flips a contiguous block of digits from 0 to 1 or 1 to 0. Your task is to determine the minimum number of operations required to make the binary string uniform (i.e. all digits are the same).

For any binary string s, the process can be visualized by counting the number of transitions between 0 and 1. If the string is already uniform, no operations are needed. Otherwise, the minimum number of flips required is given by:

[ \text{operations} = \frac{\text{transitions} + 1}{2} ]

Note that the formula works because each flip can fix two adjacent blocks. You will be given several binary strings as input.

inputFormat

The first line of input contains an integer T representing the number of binary strings. Each of the following T lines contains a binary string consisting only of characters '0' and '1'.

outputFormat

For each binary string, output a single integer representing the minimum number of operations needed to make the string uniform. Each result should be printed on a new line.

## sample

1
11111

0

</p>