Minimum Splits to Unique Substrings

You are given a string s. Your task is to find the minimum number of split operations required such that every resulting substring has at most one unique character. In a split operation, you essentially break the string into two parts. The objective is to count the number of splits required so that within each segment, all characters are the same.

For example, consider the string aaabbbcc. Splitting it into aaa, bbb, and cc yields segments where each segment contains only one type of character, so the number of splits is 2. Similarly, the string abcabc requires 5 splits.

Note: An empty string requires 0 splits.

inputFormat

The input is read from standard input (stdin). The first line contains an integer T, representing the number of test cases. Each of the following T lines contains a single string s.

outputFormat

For each test case, output the minimum number of split operations required on a separate line. The output should be written to standard output (stdout).

## sample

3
aaabbbcc
aabbcc
abcabc

2
2
5

</p>