Beautiful String Transformation

You are given a string S. Your task is to determine the minimum number of changes required to transform S into a beautiful string. A string is considered beautiful if no two consecutive characters are the same.

For each position in the string (except the first character), if the character is the same as the previous one, you must change it. The total number of changes needed is simply the count of these occurrences.

For example, the string aab requires 1 change, because the consecutive a's require breaking. Similarly, aabb requires 2 changes, while abcabc already meets the criteria and requires 0 changes.

Note: If an equation or formula is needed, use the LaTeX format. In this problem, the number of changes is defined as \[ \text{changes} = \sum_{i=2}^{n} \mathbf{1} (S_i = S_{i-1}), \] where \(\mathbf{1}(\cdot)\) is the indicator function that equals 1 when the condition is true and \(n\) is the length of the string.

inputFormat

The input begins with an integer T (1 ≤ T ≤ 10⁵) on the first line, representing the number of test cases. Each of the following T lines contains a non-empty string S consisting only of lowercase English letters. The total length of all strings is at most 10⁶.

outputFormat

For each test case, output a single integer on a new line – the minimum number of changes required to make the string beautiful.

## sample

3
aab
aabb
abcabc

1
2
0

</p>