在本题中，有效的正则表达式定义如下。在以下描述中，$E_1, E_2$ 等表示（不一定不同）有效的正则表达式。

• 十进制数字：即 $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$ 中的一个。
• 连接：$E_1E_2$。
• 析取：$(E_1|E_2|\dots|E_N)$，至少包含两个表达式。注意外层括号是必须的。
• 重复：$(E_1)^*$。注意外层括号是必须的。

例如，$7, 23, (7)^*, (45)^*, (1|2|3), ((2)^*|3), (1|2|3)$ 和 $((0|1))^*$ 都是有效的表达式。而 $(7), 4|5, 4^*, (1|)$ 和 $(0|1)^*$ 则不是。

我们称一个表达式 $E$ 匹配一个数字字符串 $D$，当且仅当以下至少一条成立：

• $E = D$。
• $E = E_1E_2$，且存在 $D_1$ 和 $D_2$ 使得 $D = D_1D_2$，且 $E_1$ 匹配 $D_1$，$E_2$ 匹配 $D_2$。
• $E = (E_1|E_2|\dots|E_N)$，且至少有一个 $E_i$ 匹配 $D$。
• $E = (E_1)^*$，且存在某个非负整数 $N$，以及 $D_1, D_2, \dots, D_N$，使得 $D = D_1D_2\dots D_N$，且 $E_1$ 匹配每一个 $D_i$。特别地，注意 $(E_1)^*$ 匹配空字符串。

例如，表达式 $((1|2))^*3$ 匹配 $3, 13, 123$ 和 $2221123$ 等字符串。然而，它不匹配 $1234, 3123, 12$ 或 $33$ 等字符串。

给定一个有效的正则表达式 $R$，请问在 $A$ 到 $B$（包含 $A$ 和 $B$）之间，有多少个整数的十进制表示（无前导零）能被 $R$ 匹配？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 个测试用例；每个测试用例包含两行。第一行包含两个正整数 $A$ 和 $B$：我们感兴趣的整数范围的闭区间。第二行包含一个字符串 $R$，仅由字符 $0123456789()|*$ 组成，保证其为上述定义中的有效正则表达式。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是在闭区间 $[A, B]$ 中能被正则表达式 $R$ 匹配的整数个数。

数据范围

$1 \le T \le 100$。 $1 \le A \le B \le 10^{18}$。 $1 \le \text{length of } R \le 30$。

小数据范围（测试集 1 - 可见）

$R$ 不包含 | 字符。

大数据范围（测试集 2 - 隐藏）

无额外限制。

样例

样例输入 1

8
1 1000
(0)*1(0)*
379009 379009
379009
1 10000
(12)*(34)*
4 5
45
1 100
((0|1))*
1 50
(01|23|45|67|23)
1 1000000000000000000
((0|1|2|3|4|5|6|7|8|9))*
1 1000
1(56|(((7|8))*9)*)

样例输出 1

Case #1: 4
Case #2: 1
Case #3: 5
Case #4: 0
Case #5: 4
Case #6: 2
Case #7: 1000000000000000000
Case #8: 6

说明

注意样例 5 到 8 不会出现在小数据范围中。

在样例 1 中，匹配范围内的数字为 1, 10, 100 和 1000。 在样例 2 中，匹配范围内的数字为 379009。 在样例 3 中，匹配范围内的数字为 12, 34, 1212, 1234 和 3434。 在样例 4 中，范围内没有匹配的数字。 在样例 5 中，匹配范围内的数字为 1, 10, 11 和 100。 在样例 6 中，匹配范围内的数字为 23 和 45。 在样例 7 中，可以形成范围内的任意数字。 在样例 8 中，匹配范围内的数字为 1, 19, 156, 179, 189 和 199。