Minimum Replacements to Avoid Adjacent Duplicates

Given a string, determine the minimum number of character replacements required so that no two adjacent characters are the same. In each replacement, you can change a character to any other character. The aim is to eliminate all occurrences of adjacent duplicate characters with the fewest substitutions.

For example, given the string aab, one replacement is needed because one of the adjacent 'a's has to be changed. The number of replacements for a string S can be computed using the formula: $$\text{Replacements} = \sum_{i=1}^{|S|-1} \mathbb{1}(S_i = S_{i+1}),$$ where $$\mathbb{1}(\cdot)$$ is the indicator function.

inputFormat

The first line of input contains an integer t representing the number of test cases. Each of the following t lines contains a single string for which you need to calculate the minimum number of required replacements.

outputFormat

For each test case, output a line with a single integer indicating the minimum number of character replacements needed so that no two consecutive characters are the same.## sample

3
aab
aaaa
abc

1
3
0