[SCOI2007]排列perm

给一个数字串 $s$ 和正整数 $d$，统计 $s$ 有多少种不同的排列能被 $d$ 整除（可以有前导零）。

例如 $123434$ 有 $90$ 种排列能被 $2$ 整除，其中末位为 $2$ 的有 $30$ 种，末位为 $4$ 的有 $60$ 种。

输入格式

第一行是一个整数 $T$，表示测试数据的个数。

以下每行一组 $s$ 和 $d$，中间用空格隔开。$s$ 保证只包含数字 $0\sim 9$。

输出格式

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

样例输入

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

样例输出

1
3
3628800
90
3
6
1398

样例解释

在前三个例子中，排列分别有 $1$、$3$、$3628800$ 种，它们都是 $1$ 的倍数。

数据范围

对于 $100\%$ 的数据：

• $s$ 的长度不超过 $10$；
• $1\le d\le 1000$；
• $1\le T\le 15$。

来源与许可

本题为 SCOI 2007 试题「排列perm」，题面与测试数据整理自 BZOJ 1072。

样例 1

输入

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

输出

1
3
3628800
90
3
6
1398