Minimum Removals for Strictly Increasing Strings

Given a string S consisting of lowercase English letters, you are allowed to remove one or more contiguous substrings. The goal is to obtain a string R such that every adjacent pair of characters satisfies the strict inequality \(R_i < R_{i+1}\) (in lexicographical order). In other words, the resulting string must be strictly increasing.

Your task is to compute the minimum number of removals needed to achieve this. If the string is already strictly increasing (or empty), no removals are needed.

Note: Removing a contiguous substring means selecting any consecutive segment of characters and deleting it entirely from the string.

inputFormat

The input is given in the following format:

T
S1
S2
...
ST

Here, T is an integer denoting the number of test cases, and each S is a non-negative string of lowercase English letters. The string can be empty.

outputFormat

For each test case, output a single line containing the minimum number of contiguous substrings that need to be removed so that the resulting string is strictly increasing.

## sample

3
abc
aa
bacd

0
1
1

</p>