A – Number Coding

In a special coding proposed by ACM group of Shiraz University, each integer number can be represented by the number of its prime factors followed by the frequency numbers of factors arranged in an increasing order. For example, 32=2⁵ has only 1 prime factor and its frequency is 5. So, it can be represented by 15. Also, 43560=2³×3²×5¹×11² has 4 factors with frequencies 3, 2, 1 and 2, hence coded as 41223. As another example, 7168 is coded into 2110. Considering only 9 prime factors {2, 3, 5, 7, 11, 13, 17, 19, 23} and given a coded number C, you should identify how many numbers share the coded representation C.

Input

The first line of the input contains an integer T as the number of test-cases. Each following line gives a code word C which will not exceed 20 characters.

Output

Print for each test-case, in a separate line, the number of possible integers that have identical translation C.

Sample Input	Sample Output
4 123 213 31312 311111	9 72 504 504