Minimum Changes to Avoid Adjacent Duplicates

You are given a string s. Your task is to determine the minimum number of changes required so that no two adjacent characters in the string are identical. In one change, you can replace a character with any other character. It can be shown that the optimal strategy is to consider each contiguous block of identical characters of length L and change \(\lfloor L/2 \rfloor\) characters.

You will be given multiple test cases. For each test case, output the minimum number of changes required.

Examples:

• For s = "abba", there is one adjacent duplicate pair ("bb"), so the answer is 1.
• For s = "aaaa", the optimal changes is \(\lfloor 4/2 \rfloor = 2\).
• For s = "ababab", no two adjacent characters are the same, so the answer is 0.

inputFormat

The first line contains an integer T (1 ≤ T ≤ 10⁵), the number of test cases.

Each of the next T lines contains a string s consisting of lowercase English letters.

The total length of all strings does not exceed 10⁶.

outputFormat

For each test case, output the minimum number of changes required on a new line.

1
abba

1