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.
import math
listx=[0]*10
def no(x):
    i=int(x)-1
    el=0
    while(i>=0):
        el+=listx[i]
        i-=1
    return el
t=int(raw_input().strip())
while t:
    t-=1
    ans=1
    listx=[0]*10
    num=raw_input().strip()
    for i in num:
        listx[int(i)]+=1
    leng=len(num)-1
    i=0
    while leng>0:
        temp=no(num[i])*math.factorial(leng)
        if(temp>0):
            for x in listx:
                temp/=math.factorial(x)
        ans+=temp
        listx[int(num[i])]-=1
        leng-=1
        i+=1
    ans+=no(num[i])
    print(ans)