Minimum Operations to Form Lexicographically Smallest String

The problem asks you to determine the minimum number of operations required to transform a given string into its lexicographically smallest permutation by using a reversal operation. In a single operation, you may reverse any substring of the string. By comparing the given string with its fully sorted version, the number of differing positions can be computed. The minimum number of operations is then calculated using the formula: \(\lfloor \frac{d}{2} \rfloor\), where \(d\) is the number of positions where the character in the given string and the sorted string differ.

For example, consider the string dcbae. Its sorted version is abcde. Comparing the two strings, there are 4 mismatched positions, so the answer is \(\lfloor\frac{4}{2}\rfloor = 2\). This problem tests your understanding of string manipulation, sorting, and basic greedy corrections.

inputFormat

The first line contains an integer T (1 ≤ T ≤ 100), representing the number of test cases. Each test case consists of two lines:

• The first line contains an integer n (1 ≤ n ≤ 1000), the length of the string.
• The second line contains a string of length n consisting of lowercase English letters.

outputFormat

For each test case, output a single integer on a new line that represents the minimum number of operations required to transform the string into its lexicographically smallest permutation.

## sample

3
5
dcbae
3
abc
6
abbcca

2
0
1

</p>