Minimum Deletions to Make Alternating String

Given a string s, your task is to determine the minimum number of deletions required to transform the string into one where no two adjacent characters are the same. In other words, ensure that the string becomes an alternating sequence.

Consider the string $s$. You need to remove as few characters as possible such that for every index $i$ ($1 \leq i < |s|$), $s_i \neq s_{i+1}$.

For example, if $s = \texttt{AAAA}$, then you need to delete 3 characters to get \texttt{A}. Similarly, for $s = \texttt{ABABABAB}$, the string is already alternating and requires no deletions.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

(T) -- the number of test cases (an integer).
Following this, there are (T) lines, each containing a single string (s).

For each test case, you need to compute the minimum number of deletions required.

outputFormat

For each test case, print on a new line the minimum number of deletions required to make the string alternating. The output should be sent to standard output (stdout).## sample

3
AAAA
BBBBB
ABABABAB

3
4
0