Description

在本题中，一个合法的正则表达式是下列之一。描述中的 $E_1, E_2$ 等表示（不一定不同的）合法正则表达式。

• 一个十进制数字：即 $\mathbf{0}\ \mathbf{1}\ \mathbf{2}\ \mathbf{3}\ \mathbf{4}\ \mathbf{5}\ \mathbf{6}\ \mathbf{7}\ \mathbf{8}\ \mathbf{9}$ 之一。
• 连接：$E_1 E_2$。
• 并选：$\left(E_1|E_2|\ldots|E_N\right)$，其中至少有两个表达式。注意外层括号是必须的。
• 重复：$\left(E_1\right)^*$。注意外层括号是必须的。

例如，$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_1 E_2$，且存在 $D_1, D_2$ 使得 $D=D_1 D_2$ 且 $E_i$ 匹配 $D_i$。
• $E=\left(E_1|E_2|\ldots|E_N\right)$，且至少有一个 $E_i$ 匹配 $D$。
• $E=\left(E_1\right)^*$，且存在若干非负整数 $N$ 及 $D_1, D_2, \ldots, D_N$，使得 $D=D_1 D_2 \ldots D_N$ 且 $E_1$ 匹配每个 $D_i$。特别地，$\left(E_1\right)^*$ 匹配空串。

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

给定一个合法的正则表达式 $\mathbf{R}$，问有多少个整数在 $[\mathbf{A}, \mathbf{B}]$ 间，其十进制表示（无前导零）能被 $\mathbf{R}$ 匹配？

Input Format

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例数量。接下来有 $\mathbf{T}$ 组测试用例，每组包含两行。第一行为两个正整数 $\mathbf{A}$ 和 $\mathbf{B}$，表示所关心的整数区间（闭区间）。第二行为一个仅由 0123456789()|* 组成的字符串 $\mathbf{R}$，保证其为合法正则表达式（如上所述）。

Output Format

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

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)*)

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

Hint

样例解释

注意，样例 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$。

限制条件

• $1 \leqslant \mathbf{T} \leqslant 100$。
• $1 \leqslant \mathbf{A} \leqslant \mathbf{B} \leqslant 10^{18}$。
• $1 \leqslant \mathbf{R}$ 的长度 $\leqslant 30$。

小数据集（15 分，测试集 1 - 可见）

• $\mathbf{R}$ 不包含 | 字符。

大数据集（15 分，测试集 2 - 隐藏）

• 无其他限制。

翻译由 GPT4.1 完成。