Min Operations to Balance String

You are given a string consisting of uppercase and lowercase English letters. Your task is to determine the minimum number of operations required to convert the string into a balanced string.

A string is considered balanced if:

• The number of uppercase letters is equal to the number of lowercase letters.
• It is possible to rearrange the characters so that they form an alternating sequence of uppercase and lowercase letters.

In one operation, you can change the case of any single letter (i.e. from uppercase to lowercase or vice versa).

The required number of operations for each test case is given by the formula \[ \text{operations} = \left\lfloor \frac{|U - L|}{2} \right\rfloor, \] where U and L denote the number of uppercase and lowercase letters in the string respectively.

Read the input from stdin and output the answer for each test case to stdout.

inputFormat

The first line of input contains a single integer T indicating the number of test cases.

This is followed by T lines, each containing a non-empty string s composed of uppercase and lowercase English letters.

Example:

3
aA
bbbB
AbCdEf

outputFormat

For each test case, output a single integer on a separate line representing the minimum number of operations required to convert the given string into a balanced string.

Example:

0
1
0

## sample

3
aA
bbbB
AbCdEf

0
1
0

</p>