In this problem, a valid regular expression is one of the following. In the following descriptions, , , etc. denote (not necessarily different) valid regular expressions.
- A decimal digit: that is, one of .
- Concatenation: .
- Disjunction: , for at least two expressions. Note that the outer parentheses are required.
- Repetition: . 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 matches a string of digits if and only if at least one of the following is true:
- .
- and there exist and such that and matches .
- and at least one of the matches .
- and there exist for some non-negative integer such that and matches each of the .
In particular, note that 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 , for how many integers between and , inclusive, does match the integer's base representation (with no leading zeroes)?
Input Specification
The first line of the input gives the number of test cases, . test cases follow; each consists of two lines. The first line has two positive integers and : the inclusive limits of the integer range we are interested in. The second has a string consisting only of characters in the set 0123456789()|*
, which is guaranteed to be a valid regular expression as described in the statement above.
Output Specification
For each test case, output one line containing the number of integers in the inclusive range that the regular expression matches.
Limits
Sample Input
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)*)
Sample Output
4
1
5
0
4
2
1000000000000000000
6
Comments