Description

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$.

Input Format

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$.

Output Format

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

7
000 1
001 1
1234567890 1
123434 2
1234 7
12345 17
12345678 29

1
3
3628800
90
3
6
1398

Hint

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