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 ~0, 1, 2, 3, 4, 5, 6, 7, 8, 9~.
• Concatenation: ~E_1 E_2~.
• Disjunction: ~(E_1 | E_2 | \dots | E_N)~, for at least two expressions. Note that the outer parentheses are required.
• Repetition: ~(E_1)*~. 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_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 = (E_1 | E_2 | \dots | E_N)~ and at least one of the ~E_i~ matches ~D~.
• ~E = (E_1)*~ and there exist ~D_1, D_2, \dots, D_N~ for some non-negative integer ~N~ such that ~D = D_1 D_2 \dots D_N~ and ~E_1~ matches each of the ~D_i~.

In particular, note that ~(E_1)*~ 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)?

Input Specification

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.

Output Specification

For each test case, output one line containing the number of integers in the inclusive range ~[A, B]~ that the regular expression ~R~ matches.

Limits

~1 \le T \le 100~

~1 \le A \le B \le 10^{18}~

~1 \le |R| \le 30~

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