Minimum Swaps to Sort a String

You are given a string s of length n. Your task is to determine the minimum number of adjacent swaps required to sort the string in non-decreasing order. In other words, you should rearrange the characters so that s becomes sorted, and you can only swap adjacent characters.

If the string is already sorted, the answer is 0. Note that any string can be sorted by adjacent swaps, so the output is always a non-negative integer. The number of swaps required is equivalent to the number of inversions in the string. An inversion is a pair of indices \( (i, j) \) such that \( i < j \) and \( s[i] > s[j] \). Using a merge sort based approach, the inversion count can be computed in \( O(n \log n) \) time.

Formally, given a string \( s \), you need to compute the inversion count \( I(s) \). For each test case, output the minimum number of swaps needed, which is \( I(s) \) if the string is not already sorted, and \( 0 \) otherwise.

Note: Each test case is independent.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains an integer \( T \), the number of test cases.
2. Each test case consists of two lines:
   1. The first line contains an integer \( n \) denoting the length of the string.
   2. The second line contains the string \( s \) of length \( n \).

outputFormat

For each test case, output the minimum number of adjacent swaps needed to sort the string. Each answer should be printed on a separate line to stdout.

## sample

3
4
dcba
5
aabcc
3
bca

6
0
2

</p>