我们有一个由十进制数字组成的字符串 $S$。$S$ 的一个划分是通过将 $S$ 分割成若干个连续的子串而创建的。例如，如果 $S$ 是 $0145217$，两种可能的划分为 $014\ 5\ 21\ 7$ 和 $0\ 14\ 52\ 17$。每个数字必须恰好被使用一次，且每个子串必须非空。如果 $S$ 有 $L$ 位数字，则它共有 $2^{L-1}$ 种可能的划分。

给定一个正整数 $D$，$S$ 的一个划分被称为可被 $D$ 整除，如果对于每一对相邻的子串，它们所表示的十进制整数中至少有一个能被 $D$ 整除。如果 $D=7$，上述第一个划分是可被整除的，因为 $014$、$21$ 和 $7$ 所表示的整数都能被 $7$ 整除。第二个划分不可被整除，因为 $52$ 和 $17$ 是相邻子串，且它们所表示的整数都不能被 $7$ 整除。将 $0145217$ 划分为 $0145217$ 本身是可被任何 $D$ 整除的，因为不存在相邻的子串对。

给定 $S$ 和 $D$，计算 $S$ 有多少种可被 $D$ 整除的划分。由于输出可能非常大，我们仅要求你输出结果除以质数 $10^9+7$ ($1000000007$) 的余数。

输入格式

第一行输入包含测试用例的数量 $T$。接下来有 $T$ 行。每行代表一个测试用例，包含一个数字字符串 $S$ 和一个正整数 $D$。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 $S$ 可被 $D$ 整除的划分数量，对质数 $10^9+7$ ($1000000007$) 取模。

数据范围

$1 \le T \le 100$。 $1 \le D \le 10^6$。

子任务 1 $1 \le |S| \le 1000$。

子任务 2 $1 \le |S| \le 10^5$。

样例

样例输入 1

3
0145217 7
100100 10
5555 12

样例输出 1

Case #1: 16
Case #2: 30
Case #3: 1

说明

在样例 1 中，$S$ 的所有 16 种可被整除的划分如下： $0145217$，$0\ 145217$，$0\ 14\ 5217$，$0\ 14\ 5\ 217$，$0\ 14\ 5\ 21\ 7$，$0\ 14\ 521\ 7$，$0\ 145\ 217$，$0\ 145\ 21\ 7$，$0\ 14521\ 7$，$014\ 5217$，$014\ 5\ 217$，$014\ 5\ 21\ 7$，$014\ 521\ 7$，$0145\ 217$，$0145\ 21\ 7$ 以及 $014521\ 7$。

在样例 2 中，总共有 $2^5 = 32$ 种划分方式。为了使两个相邻子串都不被 $10$ 整除，我们需要它们都不以 $0$ 结尾。唯一满足条件的划分方式是 $1\ 001\ 00$ 和 $1\ 001\ 0\ 0$，这意味着 $S$ 的其余 30 种划分都是可被 $10$ 整除的。

在样例 3 中，没有任何子串表示的整数是偶数，这意味着它们都不能被 $12$ 整除。因此，要避免出现两个相邻子串都不被 $12$ 整除的情况，唯一的方法就是不出现相邻子串，这只有 1 种方式：$5555$。