Hide

Problem A
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:

\[ f(x,y) = \left\{ \begin{array}{ll} f(x-a_1,y-b_1)+f(x-a_2,y-b_2)+\ldots +f(x-a_ n,y-b_ n)+c, & \text {if $x, y > 0$} \\ d, & \text {otherwise} \end{array} \right. \]

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.

Sample Input 1 Sample Output 1
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

Please log in to submit a solution to this problem

Log in