The Head Chef has received his id from the Association of Byteland . He wants to know the numerical rank of his number among the numbers that can be formed by the exact same digits ( i.e. among numbers having same number of 0's , 1's ... 9's as his id ) . Note that id's can start with 0 . Given a number, find the rank of the number .

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case contains a single integer N denoting the id the chef has received .

Output

For each test case, output a single line containing the answer to the given test case .

Constraints

1 ≤ T ≤ 10000
1 ≤ number of digits in N ≤ 18

Example
Input:
2
276
762

Output:
2
6

Explanation
Example case 1.The numbers that can be formed with one '2' ; one '7' and one '6' in increasing order are :
267
276
627
672
726
762
The rank for 276 is 2 and rank for 762 is 6.

见题面

见题面