Minimal Operations on Binary Strings

You are given a string consisting only of the characters 'a' and 'b'. Your task is to determine the minimal number of operations required to transform the string such that it contains at most one contiguous segment of 'a's and at most one contiguous segment of 'b's.

An operation is defined as the process of merging two contiguous segments into one by changing the boundary between the segments. In other words, if a string changes character (from 'a' to 'b' or from 'b' to 'a'), it counts as a transition. The minimal number of operations required can be mathematically expressed as follows:

[ \text{operations} = \left\lceil \frac{\text{transitions}}{2} \right\rceil, ]

where transitions is the number of times the character in the string changes from one character to the other.

If the string is empty, no operations are needed.

inputFormat

The input is given from the standard input (stdin) and consists of multiple lines:

• The first line contains a single integer t representing the number of test cases.
• The following t lines each contain a string composed solely of the characters 'a' and 'b'.

outputFormat

For each test case, output a single integer on a new line which is the minimal number of operations required so that the string contains at most one contiguous segment of 'a's and at most one contiguous segment of 'b's.

The output should be printed to the standard output (stdout).

## sample

3
abba
abab
aaa

1
2
0

</p>