[SCOI2007]排列

题目描述

给一个数字串 $s$ 和正整数 $d$, 统计 $s$ 有多少种不同的排列能被 $d$ 整除(可以有前导 $0$)。例如 $123434$ 有 $90$ 种排列能被 $2$ 整除,其中末位为 $2$ 的有 $30$ 种,末位为 $4$ 的有 $60$ 种。

输入输出格式

输入格式


输入第一行是一个整数 $T$,表示测试数据的个数,以下每行一组 $s$ 和 $d$,中间用空格隔开。$s$ 保证只包含数字 $0,1,2,3,4,5,6,7,8,9$。

输出格式


每个数据仅一行,表示能被 $d$ 整除的排列的个数。

输入输出样例

输入样例 #1

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

输出样例 #1

1
3
3628800
90
3
6
1398

说明

$100\%$ 的数据满足:$s$ 的长度不超过 $10$,$1\le d\le 1000$,$1\le T\le 15$。 在前三个例子中,排列分别有 $1,3,3628800$ 种,它们都是 $1$ 的倍数。