Minimum Changes to Create a Balanced String

You are given a string s consisting of lowercase letters. The task is to determine the minimum number of changes needed to transform s into a balanced string, where a balanced string is defined as one in which no two adjacent characters are identical.

Formally, for a string \( s = s_0 s_1 \dots s_{n-1} \), you need to compute the value:

[ \text{min_changes}(s) = \sum_{i=1}^{n-1} \mathbf{1}{{s_i = s{i-1}}}, ]

where \( \mathbf{1}_{\{s_i = s_{i-1}\}} \) is 1 if \( s_i = s_{i-1} \) and 0 otherwise. For example, in the string "aabb", you need to make 2 changes (one for each pair of identical adjacent characters) to ensure no two adjacent characters are the same.

The input begins with an integer representing the number of test cases. Each test case consists of a single string for which you need to compute the answer.

inputFormat

The first line contains an integer t (\(1 \le t \le 10^5\)) representing the number of test cases. Each of the following t lines contains a non-empty string s made up of lowercase letters, where \(1 \le |s| \le 10^5\).

outputFormat

For each test case, output a single integer that denotes the minimum number of changes required to convert the string into a balanced string. Each answer should be printed on a new line.

## sample

5
aabb
abcd
aaaa
abab
aab

2
0
3
0
1

</p>