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