Minimum Moves to Make a Beautiful String

Your task is to find the minimum number of moves required to transform a given string into a beautiful string. A beautiful string is defined as one in which no two adjacent characters are the same. In a single move, you can remove one character from a pair of consecutive identical characters.

For example, for the string AABBCC, you can remove one character from each duplicate pair to obtain a string with no adjacent duplicates. Your goal is to determine the minimum number of such moves required for each test case.

Note: The allowed operation is to remove a character from a pair of adjacent duplicate characters.

inputFormat

The input begins with a line containing a single integer t — the number of test cases. Each of the next t lines contains a single string s composed of uppercase English letters.

outputFormat

For each test case, output one integer on a new line, representing the minimum number of moves needed to transform the string into a beautiful string.

## sample

3
AABBCC
ABCABC
AAB

3
0
1

</p>