魔力项链

时间限制：0.5s
内存限制：128MB

题目描述

作为一个非主流魔法师，小猴从来不使用魔杖，而是依靠魔力项链来发动各种奇妙的魔法。魔力项链最多有 $10$ 种宝石，分别对应数字 $0$ ~ $9$，相同种类的宝石之间没有区别。每当小猴需要使用魔法时，他需要重新排列项链上的宝石。

一串魔力项链，可以用一个数字串 $S$ 表示，小猴需要用这条项链发动的魔法魔力值为 $d$。只有项链排列出的十进制数字恰好是 $d$ 的倍数时，魔法才能准确发动。例如项链是 $223$，魔力值是 $2$，一共有 $2$ 种排列能成功发动魔法，分别是 $232$ 和 $322$。

现在，小猴有 $T$ 串魔力项链，每串项链都要发动一个魔法，为了锻炼自己的施法速度，小猴希望你能帮他算出每串项链有多少种排列方法，使得排列后的数字串是对应魔力值的倍数。（项链的开头可以为 $0$）

输入格式

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

输出格式

每一组输出一行，表示魔力项链可行的排列数量。

输入输出样例 #1

输入#1

7
111 1
100 1
1234567890 2
123434 2
1234 7
54321 17
87654321 29

输出#1

1
3
1814400
90
3
6
1398

说明提示

【样例说明】

在前两个项链中，排列分别有 $1,3$ 种，都是 $1$ 的倍数。

第三个项链有 $3628800$ 种排列，其中一半是 $2$ 的倍数。

数据范围

$100\%$ 的数据满足：$S$ 的长度不超过 $10$，$1\le d\le 1000$，$1\le T \le 15$。