I I U P C 2 0 0 6

Problem A: Anagram Division

Input: standard input
Output: standard output

 

Given a string s and a positive integer d you have to determine how many permutations of s are divisible by d.

 

Input

First line of the input contains one integer T the number of test cases. Each of the test cases is one line containing s and d separated by a single space.

 

Output

For each test case output contains an integer the number of permutations of s that are divisible by d.

 

Constraints

-           s contains only digits.
-           The length of s is between 1 and 10 inclusive.
-           d is a positive integer between 1 and 10000.

 

Sample Input

Output for Sample Input

3
000 1
1234567890 1
123434 2

1
3628800
90

 

Problemsetter: Abdullah Al Mahmud