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, , and are valid expressions. , and 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 matches , and , among other strings. However, it does not match or , among other strings.
Given a valid regular expression , for how many integers between and , inclusive, does match the integer's base 10 representation (with no leading zeroes)?
输入格式
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.
输出格式
For each test case, output one line containing Case #x: y, where is the test case number (starting from 1) and is the number of integers in the inclusive range that the the regular expression matches.
