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 image.

Example

Input:
5
4 4 2 2 1 0 2 1 2 3 4
4 4 1 1 3 1 1 2 2 2 2
6 10 3 2 2 0 0 5 4 3 2
16 18 5 1 5 10 8 21 27 29 87
14 15 12 4 4 3 5 84 74 53 68

Output:
Case #1: 7
Case #2: 15
Case #3: 32
Case #4: 197
Case #5: 16

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