Description
Domo is a brilliant dog. By the way, he is pretty good at running races.
This day, Domo attends another running race. But this race uses a special rule for all participants.
The distance each participant needs to run is different, it depends on the permutation of the participant's name and the minimum one in alphabetical order.
For example, there's a participant called "cab". Since all the permutations in "cab" in the alphabetical order are:
We need to calculate the distance between the minimum one in the alphabetical order and the original name, which is "abc" and "cab".
As a result, the distance "cab" need to run in this competition is 4.
Now, given a series of names, please calculate the distance they need to run, so we can know if Domo has a chance to win the champion.
Hint: If you find it hard to pass test cases 7 and 8, try to find out why recursion spends a lot of time and see if there is a solution without using recursion!
Input
The first line contains an integer T - the number of participants in this race.
For the following T lines, each line contains a string S - the name of each participant.
The variable range of each test case is different.
For the test case 1 ~ 2, 1 ≤ T ≤ 102, 1 ≤ the length of S ≤ 5.
For the test case 3 ~ 6, 1 ≤ T ≤ 103, 1 ≤ the length of S ≤ 8.
For the test case 7 ~ 8, 1 ≤ T ≤ 104, 1 ≤ the length of S ≤ 15.
Note that each participant's name is in lower case, and will not have any repetitive letters. For example, "Domo" is invalid, since the letter 'o' is repeated... Wait, how does Domo attend this competition?
Output
Print the distance each participant needs to run one per line.