P13206 [GCJ 2016 Finals] Integeregex

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.

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