Ping Pong Balls (Large)

A large room is packed with mousetraps arranged in a grid. Every mousetrap holds two ping pong balls, placed so that when the trap goes off the balls fly out, land on other mousetraps, and set those off. The walls of the room are sticky, so a ball that hits a wall stays there.

Every mousetrap that goes off throws its balls the same way. The two landing spots are given by an $x$ displacement and a $y$ displacement measured from the trap that just went off. You throw a single ping pong ball into the room. It hits one mousetrap and sets it off, the two balls that fly out set off two more mousetraps, and then four balls fly out. When the dust settles many mousetraps have gone off, but some were never touched by any ball. A ball that lands on a mousetrap that already went off does nothing.

Count the mousetraps that go off.

In a room of width 5 and height 3, with the two displacements $(-1, 0)$ and $(-1, -1)$, a first ball that hits the mousetrap at $(4, 2)$ sets off 12 mousetraps, as the picture below shows.

The first line contains the number of test cases $C$. Each test case takes four lines. The first line holds the size of the mousetrap grid, which is also the size of the room: the width $W$ and the height $H$. The next two lines hold the displacements of the two ping pong balls, one per line, as an $x$ component and a $y$ component. For example, if these two lines are 0 1 and 1 1, then a trap that goes off sends one ball to the mousetrap directly above it and the other to the mousetrap up and to the right. The last line holds the column $X$ and the row $Y$ of the mousetrap hit by the first ball. The bottom left mousetrap is 0 0.

The limits are:

• $1 \le C \le 100$
• $2 \le W, H \le 10^6$
• the $x$ and $y$ components of both displacements are integers between $-20$ and $20$
• neither displacement vector is the zero vector
• $0 \le X < W$, $0 \le Y < H$

For each test case, print one line of the form Case #A: B, where $A$ is the 1-based number of the test case and $B$ is the number of mousetraps that go off. The mousetrap hit by the first ball counts too.