PESADA08 - Position of all-distinct-digits number in base b

You are given a b-digits-long whole number in base b where all the digits are distinct. If all such all-distinct-b-digits-long whole numbers in base b are listed in lexicographic order, what would be the position of the given number?

Input

The input begins with the number t of test cases in a single line (1 <= t <= 1000). Each test case has a all-distinct-b-digits-long number m which is in base b (2 <= b <= 10). Note that m is in base b and is b digits long where all the digits are distinct.

Output

For each test case of all-distinct-b-digits-long number m in base b, in a new line, print the position of the number if all all-distinct-b-digits-long numbers are listed in lexicographic order.

Example

Input:
8
01
10
0123
0132
3210
0123456789
0123456798
9876543210 Output: 1
2
1
2
24
1
2
3628800

Added by:Prof. Channa Bankapur
Date:2015-02-28
Time limit:1s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C

hide comments
2015-03-01 19:29:53 Prof. Channa Bankapur
It was meant to be in tutorial. Thanks for moving it.
2015-02-28 12:01:46 Mitch Schwartz
1) We already have PERMRANK.
2) There is no need for that language restriction.
--> Moved to tutorial.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.