Minimum Adjacent Swaps to Sort a String

You are given a string s consisting of lowercase English letters. In one operation, you can swap any two adjacent characters in the string. Your task is to determine the minimum number of operations required to sort the string in lexicographical order.

Formally, let the initial string be s and its sorted version be s' (i.e. the characters of s arranged in non-decreasing order). You are allowed only to swap adjacent characters. It can be shown that the minimum number of operations needed is equal to the number of inversions in the string. An inversion is a pair of indices \(i, j\) such that \(i s[j]\), which in \(\LaTeX\) is written as:

[ \text{Inversions}(s) = \sum_{0 \le i < j < n} \mathbf{1}_{{s[i] > s[j]}} ]

For example, for the string "dcba", there are 6 inversions, so the answer is 6, and for "abcd" there are 0 inversions, so no operations are needed.

inputFormat

The first line of the input contains a single integer T denoting the number of test cases.
Each of the next T lines contains a string s which you need to sort using the minimum number of adjacent swaps.

Input Format:

T
s1
s2
...
sT

outputFormat

For each test case, print a single integer representing the minimum number of adjacent swaps required to sort the string in lexicographical order.

Output Format:

result1
result2
... 
resultT

## sample

2
dcba
abcd

6
0

</p>