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 3 000 1 1234567890 1 123434 2 Sample Output 1 3628800 90