Game of Peace

Bob has learned a new magic trick that needs a very special preparation. If he masters the trick he brings peace to the world, and if he fails the world is destroyed.

The preparation works like this. There are two containers. One starts empty and the other holds $X$ marbles. Bob owns a marble cloning machine. The machine clones the marbles in the container that holds more marbles, then pours the clones into the other container. For example, if the two containers hold 7 and 4 marbles, after one cloning step they hold 7 and 11 marbles. The machine performs this cloning operation exactly $M$ times.

The machine has a bug. Right after it performs $N$ cloning operations ($N \le M$), it adds $Y$ extra marbles to the container that holds more marbles. It then continues with exactly $M - N$ more cloning operations.

During the cloning operations, if both containers hold the same number of marbles, either one can be treated as the container that holds more marbles.

Bob's friend Alice knows how to fix the machine. All he has to do is compute the greatest common divisor of the two container sizes after the machine is done. Help Bob save the world.

The first line holds a single integer $T$ ($1 \le T \le 1000$), the number of test cases. $T$ test cases follow.

Each test case is a single line with four integers separated by one space, $X$, $N$, $Y$ and $M$. The bounds are $1 \le X, Y \le 1000$, $0 \le N \le 70$ and $N \le M \le 100000$.

For each test case print one line in the form Case n: g, where $n$ is the test case number starting from 1 and $g$ is the greatest common divisor of the two container sizes after the machine is done.

For $X = 4$, $N = 3$, $Y = 6$, $M = 5$ the two containers hold, after each step, $(4, 0)$, $(4, 4)$, $(4, 8)$, $(12, 8)$, $(18, 8)$, $(18, 26)$, $(44, 26)$. The greatest common divisor of 44 and 26 is 2.