题目描述

In this problem, a valid regular expression is one of the following. In the following descriptions, $E_{1}, E_{2}$, etc. denote (not necessarily different) valid regular expressions.

• A decimal digit: that is, one of $\mathbf{0} \mathbf{1} \mathbf{2} \mathbf{3} \mathbf{4} \mathbf{5} \mathbf{6} \mathbf{7} \mathbf{8} \mathbf{9}$.
• Concatenation: $E_{1} E_{2}$.
• Disjunction: $\left(E_{1}\left|E_{2}\right| \ldots\left|E_{N}\right)\right.$, for at least two expressions. Note that the outer parentheses are required.
• Repetition: $\left(E_{1}\right)^{*}$. Note that the outer parentheses are required.

For example, $7,23, (7)^{*},(45)^{*},(1|2| 3),((2)^{*} \mid 3),(1|2| 3)$, and $((0|1))^{*}$ are valid expressions. $(7), 4|5,4^{*},(1|)$, and $(0|1)^{*}$ are not.

We say that an expression $E$ matches a string of digits $D$ if and only if at least one of the following is true:

• $E=D$.
• $E=E_{1} E_{2}$ and there exist $D_{1}$ and $D_{2}$ such that $D=D_{1} D_{2}$ and $E_{i}$ matches $D_{i}$.
• $E=\left(E_{1}\left|E_{2}\right| \ldots\left|E_{N}\right)\right.$ and at least one of the $E_{i}$ matches $D$.
• $E=\left(E_{1}\right)^{*}$ and there exist $D_{1}, D_{2}, \ldots, D_{N}$ for some non-negative integer $N$ such that $D=D_{1} D_{2} \ldots D_{N}$ and $E_{1}$ matches each of the $D_{i}$. In particular, note that $\left(E_{1}\right)^{*}$ matches the empty string.

For example, the expression $((1|2))^{*} 3$ matches $3,13,123$, and $2221123$, among other strings. However, it does not match $1234,3123,12,$ or $33$, among other strings.

Given a valid regular expression $\mathbf{R}$, for how many integers between $\mathbf{A}$ and $\mathbf{B}$, inclusive, does $\mathbf{R}$ match the integer's base 10 representation (with no leading zeroes)?

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow; each consists of two lines. The first line has two positive integers $\mathbf{A}$ and $\mathbf{B}$ : the inclusive limits of the integer range we are interested in. The second has a string $\mathbf{R}$ consisting only of characters in the set 0123456789()|*, which is guaranteed to be a valid regular expression as described in the statement above.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the number of integers in the inclusive range $[\mathbf{A}, \mathbf{B}]$ that the the regular expression $\mathbf{R}$ matches.

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

提示

Sample Explanation

Note that sample cases 5 through 8 would not appear in the Small dataset.

In sample case 1, the matches in range are $1, 10, 100$, and $1000$.

In sample case 2, the match in range is $379009$.

In sample case 3, the matches in range are $12, 34, 1212, 1234$, and $3434$.

In sample case 4, there are no matches in range.

In sample case 5, the matches in range are $1, 10, 11$, and $100$.

In sample case 6, the matches in range are $23$ and $45$.

In sample case 7, it is possible to form any number in the range.

In sample case 8, the matches in range are $1, 19, 156, 179, 189$, and $199$.

Limits

• $1 \leqslant \mathbf{T} \leqslant 100$.
• $1 \leqslant \mathbf{A} \leqslant \mathbf{B} \leqslant 10^{18}$.
• $1 \leqslant$ length of $\mathbf{R} \leqslant 30$.

Small dataset (15 Pts, Test Set 1 - Visible)

• $\mathbf{R}$ contains no | characters.

Large dataset (15 Pts, Test Set 2 - Hidden)

• No additional limits.