hackercupai/hackercup huggingface dataset:
John's friend Peter purchases a new high resolution monitor with dimension
**W** * **H** where **W** is the number of pixels in each row (i.e. width) and
**H** is the number of pixels in each column (i.e. height).

However, there are **N** dead pixels on the monitor. The **i**-th dead pixel
is located at (**x**[**i**], **y**[**i**]). (0, 0) is the top-left pixel and
(**W** \- 1, **H** \- 1) is the bottom-right pixel. The locations of the dead
pixels could be generated by 6 given integers **X**, **Y**, **a**, **b**,
**c** and **d** by the following rules. If 2 pixels are at the same location,
they are considered the same. It is possible that there are less than **N**
**distinct** dead pixels.

* **x**[0] = **X**
* **y**[0] = **Y**
* **x**[**i**] = (**x**[**i** \- 1] * **a** \+ **y**[**i** \- 1] * **b** \+ 1) % **W** (for 0 < **i** < **N**)
* **y**[**i**] = (**x**[**i** \- 1] * **c** \+ **y**[**i** \- 1] * **d** \+ 1) % **H** (for 0 < **i** < **N**)

Peter connects his monitor to his computer and opens an image with dimension
**P** (width) * **Q** (height). How many unique positions can the image be
placed so that it can be displayed perfectly (i.e. all pixels of the picture
are shown on the monitor)? The image cannot be rotated.

### Input

The first line contains an integer **T**, which is the number of test cases.
Then **T** test cases follow. Each test case contains 11 integers **W**,
**H**, **P**, **Q**, **N**, **X**, **Y**, **a**, **b**, **c**, **d**.

### Output

For each of the test cases numbered in order from 1 to **T**, output "Case #",
followed by the case number (with 1 being the first test case), followed by ":
", followed by an integer which is the number of different possible positions
for the poster.

### Constraints

* 1 ≤ **T** ≤ 20
* 1 ≤ **W**, **H** ≤ 40 000
* 1 ≤ **P** ≤ **W**
* 1 ≤ **Q** ≤ **H**
* 1 ≤ **N** ≤ min(1 000 000, **W** * **H**)
* 1 ≤ **a**, **b**, **c**, **d** ≤ **100**
* 0 ≤ ** X ** < ** W **
* 0 ≤ ** Y ** < ** H **