Program

Interview

Time limit1sMemory limit128 MB

Summary

Count the starting values from 1 to M that reach exactly A after running the given add, subtract, multiply, and floor-divide program.

Level: Medium6 of 10
Topics: Binary search, Intervals, Simulation
Solved: No attempts yet

Problem

Hektor has recently started learning the programming language C--. A program in this language operates on a single natural-number variable that is stored in memory before any command is executed.

C-- provides the following commands:

+= X : adds $X$ to the variable in memory.
-= X : subtracts $X$ from the variable in memory.
*= X : multiplies the variable in memory by $X$ .
/= X : divides the variable in memory by $X$ using integer division (rounding down).

Hektor wrote a C-- program and wants the value of the variable in memory to be exactly $A$ after the program finishes. How many initial values in the range $[1, M]$ make this possible?

Input

The first line contains the number of test cases $Z$ ( $1 \le Z \le 10$ ).

The first line of each test case contains the integers $N$ , $M$ , and $A$ ( $1 \le N \le 1000$ , $1 \le M \le 10^{18}$ , $0 \le A \le 10^{18}$ ). The next $N$ lines contain the commands of the program in order, where each $X$ satisfies $1 \le X \le 10^{18}$ .

You may assume that after every command the variable always stays within the signed 64-bit integer range and never becomes negative.

Output

For each test case, print on its own line how many initial values satisfy the condition described above.

Examples4

Example 1
Input
```
2
1 6 1
/= 3
2 10 4
+= 2
*= 3
```
Expected output
```
3
0
```
Example 2
Input
```
1
1 10 7
+= 3
```
Expected output
```
1
```
Example 3
Input
```
1
1 100 15
*= 5
```
Expected output
```
1
```
Example 4
Input
```
1
1 20 2
/= 4
```
Expected output
```
4
```