Minimum Changes to Alternate Binary String

Given a binary string, determine the minimum number of changes required to modify it into an alternating pattern (i.e., no two adjacent characters are the same). You can change any character from '0' to '1' or vice versa.

Formally, for a binary string (S) of length (n), you need to compute the minimum number of character changes so that (S) becomes either (0,1,0,1,...) or (1,0,1,0,...). This can be achieved by comparing the cost of converting (S) to the two possible alternating patterns and taking the minimum cost.

inputFormat

The first line contains an integer (T), representing the number of test cases. Each of the following (T) lines contains a non-empty binary string.

outputFormat

For each test case, output the minimum number of changes required to make the binary string alternating. Each result should be printed on a new line.## sample

1
010101

0