Dictionary

Time limit2sMemory limit512 MB

Summary

For each of the given 9-letter permutations of a through i, report its 1-based rank in lexicographic order.

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

Problem

The people of MacGuffin Island write with an alphabet of only the first nine Roman letters: a, b, c, d, e, f, g, h, i. Every word is exactly nine letters long and uses each of those letters exactly once. Every permutation of the nine letters is a word, so the language has $9! = 362880$ words.

The library of the largest temple holds a dictionary of the language, and each word takes one page. The dictionary is ordered the way an English dictionary is, so abcdefghi comes first on page 1 and ihgfedcba comes last on page 362880.

Given a list of words, report the page each one appears on.

Input

The first line contains the number of words $N$ ( $1 \le N \le 6000$ ).

Each of the next $N$ lines contains one word. Every word is a string of length 9 that uses each of the letters a through i exactly once.

Output

Print the page number of each word, one per line, in the order the words are given.

Examples2

Example 1

Input

4
abcdefgih
abcdefghi
abcdefgih
ihgfedcba

Expected output

Example 2
Input
```
1
bacdefghi
```
Expected output
```
40321
```