Lexicographic Permutation Rank

Ninja got holiday homework from his English teacher. His teacher gave him a string and told him to find the rank of the string if the string is sorted in lexicographical order.

Ninja is very new into programming, he didn’t know how to solve this question but he has to solve this question as this question has a very heavy weightage among all the questions given in holiday homework.

Ninja knows that you are a very good programmer who has practiced a lot of questions. Help Ninja!.

Note:

There will only be distinct characters in the given string.

Input Format:

First line contains an integer ‘T’ denoting the number of test cases.

First and the only line of the test case contains a string ‘S’.

Output Format:

Output contains an integer ‘X’ denoting the Lexicographic Permutation Rank of the given string.

Note:

You don’t need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 25
1 <= |S| <= 20
‘a’ <= S[i] <= ‘z’ 

Time Limit: 1 sec.

Sample Input 1:

2
abc
cba

Sample Output 1:

1
6

Explanation for Sample Test Case 1:

All permutations with string abc in the lexicographical order will be “abc”, “acb”, “bac”, “bca”, “cab”, “cba”.

Test Case 1:
“abc” will have the rank 1.

Test Case 2:
“cba”  will have rank 6.

Sample Input 2:

2
coding
string

Sample Output 2:

100
598