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.