Minimum Insertions to Avoid Adjacent Duplicates

You are given an integer \(T\) representing the number of test cases. For each test case, you are provided with a string \(S\). Your task is to determine the minimum number of characters that need to be inserted in the string so that no two adjacent characters are the same.

For a string \(S\) of length \(n\), consider the indices \(1 \leq i < n\). Every time \(S[i] = S[i-1]\), an insertion is needed between these two characters to avoid adjacent duplicates. Therefore, the answer for that test case is the total number of such adjacent duplicates.

Example:
For \(S = \texttt{\"aaaa\"}\), there are three pairs of adjacent duplicates: between indices 0-1, 1-2, and 2-3. Thus, the minimum number of insertions required is 3.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer \(T\) (\(1 \le T \le 10^5\)), representing the number of test cases.
• The following \(T\) lines each contain a non-empty string \(S\) composed of lowercase English letters.

outputFormat

For each test case, output the minimum number of insertions required on a separate line to ensure that no two adjacent characters in the string are the same. The output should be printed to stdout.

## sample

1
aaaa

3

</p>