Problem P
Generalized Recursive Functions

You have been employed by the math department to find the solutions to different recursive, integer-valued functions. Every function is of the form:

where all parameters $a_ i, b_ i, c, d$ are non-negative integers, and for each $i$, $a_ i+b_ i > 0$. Write a program that, given the parameters, determines the value of the function for various inputs $x$ and $y$.

Input

Input starts with an integer $1 \le n \le 100$, indicating the number of cases that follow. Each test case has two lines. The first line is the description $0$ to $20$ pairs of $a_ i$ and $b_ i$ values, followed by $c$ and $d$. The second line is a sequence of $1$ to $20$ pairs of inputs $x$ and $y$. All inputs are integers in the range $[0,99]$, separated within each line by spaces.

Output

For each $x, y$ input to the function, output the value $f(x,y)$. Print each output on its own line and separate functions with a blank line.

2
2 0 1 0 0 1
0 0 1 0 1 1 2 1 3 1 4 1 5 1 6 1
1 0 0 1 1 1 1 0
0 0 20 20

1
1
2
3
5
8
13
21

0
130271906898720