Minimum Adjacent Swaps to Sort a String

You are given a string S. Your task is to determine the minimum number of adjacent swap operations required to transform S into its lexicographically smallest possible string.

The lexicographically smallest string is the one obtained by sorting all characters of S in non-decreasing order. Note that even though there may be multiple ways to rearrange the string when duplicate characters are present, you must compute the minimum number of adjacent swaps required for any valid transformation.

One can simulate the following procedure for each string: iterate over every character in S (considered as a list), and for every subsequent character that is smaller than the current one, perform a swap (even if it is not immediately adjacent) and count that as a single swap. Although this procedure does not perform only adjacent swaps in its simulation, it always yields the correct minimum swap count as verified by the given examples.

For example, for S = "cba", the minimum number of swaps is 3, and for S = "abac", it is 1.

The underlying idea is to account for the minimal number of inversions that must be corrected, where an inversion is a pair (i, j) with i < j and S[i] > S[j].

Note: The input and output for each test case are provided via standard input (stdin) and standard output (stdout), respectively.

inputFormat

The first line of input contains a single integer T, representing the number of test cases.

Each of the following T lines contains a non-empty string S composed of lowercase letters.

You should read all input from standard input (stdin).

outputFormat

For each test case, output a single integer on a new line representing the minimum number of adjacent swap operations required to transform the given string into its lexicographically smallest string.

Output the result to standard output (stdout).

## sample

4
cba
abac
zyx
abc

3
1
3
0

</p>