Minimum Operations to Sort Characters

You are given a string s of length n. In one operation, you can swap two adjacent characters. Your task is to determine the minimum number of such swap operations required to sort the given string in ascending order.

The key observation is that the minimum number of adjacent swaps required to sort a string is equivalent to the number of inversions in the string. An inversion is a pair of indices \(i, j\) such that \(i s_j\). Formally, the number of operations is given by:

$$\text{swaps} = \sum_{i s_j \right]$$

Assume that the string consists of lowercase English letters. Use the standard input and output for handling multiple test cases.

inputFormat

The first line of the input contains an integer T (\(1 \leq T \leq 100\)), representing the number of test cases. For each test case, the first line contains an integer n (the length of the string). The second line contains a string s of length n.

outputFormat

For each test case, output a single line containing the minimum number of swap operations required to sort the string in ascending order.

## sample

1
4
dcba

6

</p>