Minimum Operations to Uniform String

Given a string S consisting of lowercase letters, you are allowed to perform an operation that changes a single character adjacent to a contiguous block of identical characters so that it matches that block. This operation effectively extends the contiguous block by one character. The goal is to transform the entire string into a sequence of the same character.

For example, consider a string S of length \( n \). Let \( L \) be the length of the longest contiguous substring of identical characters in S. Then the minimum number of operations required is given by:

[ \text{operations} = n - L ]

Your task is to process T test cases. For each test case, output the minimum number of operations required to make the string uniform.

inputFormat

The first line of input contains an integer T, denoting the number of test cases. Each of the following T lines contains a string S (1 ≤ |S| ≤ 100000) consisting of lowercase English letters.

outputFormat

For each test case, output a single line containing an integer: the minimum number of operations required to transform the string into a uniform string.

## sample

3
abac
aaaa
abcde

3
0
4

</p>