Given a string s and a positive integer d you have to determine how many permutations of s are divisible by d.
Input
Input starts with an integer T (≤ 200), denoting the number of test cases.
Each case contains a string s (1 ≤ slength ≤ 10) and an integer d (1 ≤ d ≤ 1001). s will only contain decimal digits.
Output
For each case, print the case number and the number of permutations of s that are divisible by d.
Sample
| Sample Input | Sample Output |
|---|---|
3 000 1 1234567890 1 123434 2 | Case 1: 1 Case 2: 3628800 Case 3: 90 |