Uniform Binary String Transformation

You are given a list of binary strings. Your task is to determine the minimum number of operations required to make each string uniform (i.e. all its characters are the same). In one operation, you may flip a single character ('0' to '1' or '1' to '0').

For each binary string, the optimal strategy is to flip all occurrences of the minority character. For example, in the string 1100, there are 2 zeros and 2 ones, so the minimum number of flips would be 2.

The input will be provided via standard input and the output should be printed to standard output.

inputFormat

The first line contains an integer T representing the number of binary strings. Each of the following T lines contains one binary string s.

Constraints:

• 1 ≤ T ≤ 10^5
• 1 ≤ |s| ≤ 10^6 (Total length of all strings does not exceed 10^6)

outputFormat

For each binary string, output a single line with the minimum number of operations required to make the string uniform.

## sample

3
1100
1001
11111

2
2
0

</p>