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