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)\ast$. 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)\ast$ 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)\ast$ 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