14339번 - Integeregex (Large) 다국어

In this problem, a valid regular expression is one of the following. In the following descriptions, E₁, E₂, etc. denote (not necessarily different) valid regular expressions.

• A decimal digit: that is, one of 0 1 2 3 4 5 6 7 8 9.
• Concatenation: E₁E₂.
• Disjunction: (E₁|E₂ |...|E_N), for at least two expressions. Note that the outer parentheses are required.
• Repetition: (E₁)*. Note that the outer parentheses are required.

For example, 7, 23, (7)*, (45)*, (1|2|3), ((2)*|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₁E₂ and there exist D₁ and D₂ such that D = D₁D₂ and E_i matches D_i.
• E = (E₁| E₂|...| E_N) and at least one of the E_i matches D.
• E = (E₁)* and there exist D₁, D₂, ..., D_N for some non-negative integer N such that D = D₁D₂...D_N and E₁ matches each of the D_i. In particular, note that (E₁)*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 R, for how many integers between A and B, inclusive, does R match the integer's base 10 representation (with no leading zeroes)?

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

Limits

• 1 ≤ T ≤ 100.
• 1 ≤ A ≤ B ≤ 10¹⁸.
• 1 ≤ length of R ≤ 30.

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 [A, B] that the the regular expression R matches.

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.