1190 - SCU-J

Time Limit : 5 Second

Memory Limit : 128 MB

Submission: 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
© 2015 HUST ACMICPC TEAM. All Right Reserved.