Minimum Removals for Non-Adjacent Duplicate Characters

You are given a string s consisting of lowercase English letters. Your task is to determine the minimum number of characters that need to be removed from the string so that no two adjacent characters are identical.

For example, consider the string "aab": Removing one of the adjacent 'a' characters results in either "ab" or "ab", both of which satisfy the requirement. In contrast, the string "aaa" requires two removals. Formally, for a given string s, compute the minimum number of characters to remove so that for every index \(i\) from \(2\) to \(n\), \(s[i] \neq s[i-1]\).

Input Format:

• The first line contains an integer \(T\) representing the number of test cases.
• Each of the following \(T\) lines contains a single string \(s\).

Output Format:

• For each test case, output a single integer, which is the minimum number of removals required, on a new line.

Note: When writing formulas, use LaTeX format. For example, the condition can be written as \(\forall i \in \{2,3,\dots,n\},\ s[i] \neq s[i-1]\).

inputFormat

The input is provided via standard input (stdin). The first line contains a single integer \(T\) which represents the number of test cases. Each of the next \(T\) lines contains a non-empty string \(s\) composed of lowercase English letters.

outputFormat

For each test case, output the minimum number of characters that must be removed on a new line via standard output (stdout).

## sample

3
aab
aaa
abcde

1
2
0

</p>