1190 - SCU-J

Time Limit: 5s Memory Limit: 128MB

Submissions: 100 Solved: 17
Description
Zerg likes counting very much. He finds that for some big integer which is divisible by a specific integer M, after you changed the order of some digits, it still can be divided by M. Now, zerg want to know the number of different permutations of N that are divisible by M. For example,consider N=1225 and M=5, there are 3 different permutations of N divisible by M: 1225,2125, and 2215.
Input
The first line is a interger T, which is the number of datasets. For each test case, a line contains two integers N and M, N will be no more than 16 digits, and M will be no more than 16. None of the digits of N will equal to 0.
Output
Only one line contains the number of different permutations of N that are divisible by M. Note the number can be rather large, but it will fit into a signed 64-bit integer. Don't count the same number twice.
Sample Input
3
133 7
994938585878792 16
123456789123456 1
Sample Output
1
22245300
20432412000
Hint
Source
SCUPC