P4163 [SCOI2007] Permutation

Given a digit string $s$ and a positive integer $d$, count how many distinct permutations of $s$ are divisible by $d$ (leading $0$ is allowed). For example, $123434$ has $90$ permutations divisible by $2$, among which $30$ end with $2$ and $60$ end with $4$.

The first line contains an integer $T$, the number of testdata. Each of the following lines contains $s$ and $d$, separated by a space. String $s$ contains only digits $0,1,2,3,4,5,6,7,8,9$.

For each testdata, output one line containing the number of permutations divisible by $d$.

Constraints: For $100\%$ of the testdata, the length of $s$ does not exceed $10$, $1 \le d \le 1000$, $1 \le T \le 15$. In the first three examples, the numbers of permutations are $1, 3, 3628800$, and they are all multiples of $1$. Translated by ChatGPT 5