Minimum Contiguous Blocks Partition

Given a string, partition it into contiguous blocks such that no two consecutive blocks start with the same character. The goal is to determine the minimum number of blocks required under this constraint. For an empty string, the answer is 0.

For example, consider the string aabcc. A valid partition is ["a", "ab", "cc"]. Here the first characters of consecutive blocks are 'a', 'a', and 'c'. Since the first two blocks both start with 'a', more blocks are needed. With an optimal partition, the minimum number of blocks required is 3.

Another example is the string abcde where no two consecutive characters are the same. Hence, the entire string forms a single valid block and the answer is 1.

Note: The condition can be mathematically described by ensuring that for a valid partition of string \( s \) into blocks \( B_1, B_2, \ldots, B_k \), if \( B_i = s[a_i:b_i] \) then \( s[a_i] \neq s[a_{i+1}] \) for all \( 1 \leq i < k \).

inputFormat

The input is read from standard input and consists of multiple lines.

• The first line contains a single integer \( T \) representing the number of test cases.
• Each of the following \( T \) lines contains a non-empty string for that test case.

outputFormat

For each test case, output a single integer on a new line denoting the minimum number of contiguous blocks required such that no two consecutive blocks have the same starting character.

## sample

3
aabcc
abcde
aaa

3
1
3

</p>