Lexicographic rank of a permutation

Interview

Time limit1sMemory limit128 MB

Summary

Given a permutation of the letters a to h, print its 1-based position in lexicographic order.

Level: Easy3 of 10
Topics: Combinatorics, Math
Solved: No attempts yet

Problem

The eight letters a, b, c, d, e, f, g, h form $8! = 40320$ permutations in total. List these permutations in lexicographic order and number them from the front:

String	Order
abcdefgh	1
abcdefhg	2
abcdegfh	3
...	...
fbhacdeg	26521
...	...
hgfedcba	40320

Given a permutation of these eight letters, write a program that prints its position in this ordering.

Input

Input arrives on standard input. The first line holds the number of test cases $T$ ( $1 \le T \le 10$ ). Each of the next $T$ lines holds one permutation, a string of length 8 that uses every lowercase letter from a to h exactly once.

Output

Write the answers to standard output. For each test case, print on its own line the position of the given permutation in lexicographic order.

Examples1

Example 1

Input

3
abcdehgf
fbhacdeg
bcedfgha

Expected output

6
26521
6034