Algebra Express

Mim is a high school algebra teacher. Just last week, she taught her students how to evaluate an expression. For example, if

Given the values of a, b, c, d and e, they can evaluate r.

Now, to test how well her students are able to do these arithmetic, she has to prepare some test. But, she do this every year, and each time she has to make same type of questions. That made her a little bored. She thinks that evaluating an expression only depends on the position of operators and variables, not the variables itself. For example in the expression above, for all possible values of a, b, c, d and e, they will all be equally hard to evaluate.

She has made some generic expressions, and a set of values, which she may use in any order (e.g. one time she may use a = 2, b = 5, another time she may use a = 5, b = 2). Now, she wants to know, the number of possible ways to assign these values, so that, the value of the expression lies within a specified limit.

Input

First line contains T, the number of test cases.

Each test case starts with three integers N(2 ≤ N ≤ 12), l, h (−10¹² ≤ l ≤ h ≤ 10¹²), the number of variables, lower limit and the upper limit of the acceptable expression values.

Next line contains N integers a_i(0 ≤ a_i ≤ 9), the value of the variables she will be using in the exam.

Next line contains the expression, where each variable is represented as ‘x’. The expression will be well formed, and will contain only the symbols ‘+’, ‘-’, ‘*’,‘(’,‘)’ and ‘x’.

Output

For each test case, output the number of different assignments, that produce results within the limit [l, h].

Note that, you will be replacing each ‘x’ with a value a_j(1 ≤ j ≤ N). Each a_j have to be used exactly once. Two assignments are considered the same, if, after replacing all ‘x’, the expressions look the same.

Sample input and output