Googlander (Small)

Time limit5sMemory limit512 MB

Summary

Count all distinct walks on an R by C grid where the walker moves straight or turns right and follows forced moves until both moves are blocked.

Level: Medium5 of 10
Topics: Backtracking, Simulation
Solved: No attempts yet

Problem

Eric Googlander is a fashion model who performs by walking on a stage of squares laid out in a grid with $R$ rows and $C$ columns. He starts on the bottom left square, facing the top edge of the stage, and performs by making a series of moves. Googlander knows only these two moves:

Take one step forward in the direction he currently faces.
Turn 90 degrees to the right, then take one step forward in the direction he faces after the turn.

Googlander does not know how to turn 90 degrees to the left.

A move is unfashionable if it would take Googlander off the stage or onto a square he has already visited. Whenever neither move is unfashionable, he may pick either one, independently of every earlier choice, but he must pick one of them. Whenever one of the two moves is unfashionable, he must make the other one. As soon as both moves are unfashionable, the show ends immediately and Googlander makes no further move. He cannot stop the show early: he must keep moving until both moves become unfashionable.

How many different paths can Googlander walk? Two paths are the same if and only if they visit the same squares in the same order.

Input

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

Limits

$1 \le T \le 100$
$1 \le R, C \le 10$
The limits guarantee that every answer fits in a 32-bit signed integer.

Output

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

Note

With $R = 1$ and $C = 1$ , Googlander cannot make any move. The only path is the trivial one made of the single starting square.

With $R = 1$ and $C = 3$ , stepping straight ahead would take him off the stage, so the only move he can make is to turn right and step. After that, turning right and stepping is unfashionable, so he steps straight ahead. Then both moves are unfashionable and the show is over. This is the only path he can take.

With $R = 3$ and $C = 3$ , the six possible paths are:

The six possible paths on a 3 by 3 stage

Examples3

Example 1

Input

Expected output

Case #1: 1
Case #2: 1
Case #3: 6

Example 2
Input
```
1
10 10
```
Expected output
```
Case #1: 48620
```

Example 3

Input

Expected output

Case #1: 1
Case #2: 1
Case #3: 1
Case #4: 2
Case #5: 48620