Minimum Flips to Unify Bulbs

Given a binary string S representing a row of bulbs, where each character is either '0' or '1', you can flip any contiguous segment of bulbs in a single operation. The goal is to make all bulbs have the same state (either all '0' or all '1') using the minimum number of flips.

The optimal strategy is to count the number of segments of consecutive '0's and '1's. The answer is the minimum of these two counts. Formally, if the string is divided into segments with counts \(c_0\) for '0' segments and \(c_1\) for '1' segments, then the minimum number of flips needed is \(min(c_0,c_1)\).

For example, for S = "110011", there are two segments of '1's and one segment of '0's, so the answer is 1.

inputFormat

The first line of input contains an integer T, the number of test cases. Each of the next T lines contains a binary string S representing the state of the bulbs.

outputFormat

For each test case, output the minimum number of flips required to make all bulbs have the same state. Each result should be printed on a new line.## sample

3
110011
101010
000

1
3
0