Googlander (Large)

Eric Googlander is a fashion model. He performs by walking on a stage made of squares that form a grid with $R$ rows and $C$ columns. He begins at the leftmost square of the bottom row, facing the top edge of the stage, and performs by making a series of moves. Googlander knows only these two moves.

1. Take one step forward in the direction he is currently facing.
2. Make a single 90 degree turn to the right, then take one step forward in the new direction he is facing.

Googlander does not know how to make a 90 degree turn to the left.

If a move would take Googlander off the stage or onto a square he has already visited, that move is unfashionable. Whenever neither of the two moves is unfashionable, he is free to choose either one, independently of any choice he has made before, but he must choose one of them. Whenever exactly one of the two moves is unfashionable, he must make the other one. If at any point both moves are unfashionable, the show ends immediately. Googlander cannot stop the show early. He must keep moving until both moves become unfashionable.

How many different paths is it possible for Googlander to walk? Two paths are the same if and only if they visit the same squares in the same order.

The first line contains the number of test cases, $T$. Each of the next $T$ lines contains two space separated integers $R$ and $C$.

Limits

• $1 \le T \le 100$
• $1 \le R, C \le 25$
• Under these limits the answer always fits in a 64 bit signed integer.

For each test case, output one line containing Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of different paths that Googlander can walk.

In the first case Googlander cannot make any move. The only path is the trivial one that consists of the single square.

In the second case he cannot take a step straight ahead, because it would take him off the stage, but he can turn right and then take a step. Once he has done so, turning right and taking a step is unfashionable, and only the step straight ahead is left. After that step no move is available and the show is over. This is the only path he can take.

In the third case these are the possible paths.