Paths of Yin and Yang (Small)

You are given a grid with $N$ rows and $M$ columns. Every cell is painted black (yin) or white (yang). Two cells are neighbors when they share an edge segment of length $1$. The grid is valid when the black cells form a path and the white cells also form a path.

A set $S$ of cells is a path when all three conditions below hold.

• $S$ is connected. From any cell of $S$ you reach every other cell of $S$ by stepping between neighbors that both belong to $S$.
• Exactly two cells of $S$ have exactly one neighbor inside $S$. These two cells are the ends of the path.
• Every other cell of $S$ has exactly two neighbors inside $S$.

In the picture below the first grid is valid. The second grid is not valid: its black cells form a path, but its white cells do not.

Given $N$ and $M$, count the valid grids. Symmetry does not matter. Two grids that differ in at least one cell count as different grids, even when a rotation or a reflection turns one into the other.

The first line contains one integer $T$, the number of test cases. Each of the next $T$ lines contains two integers $N$ and $M$ separated by a space.

For each test case print one line in the form Case #x: A, where $x$ is the test case number starting from 1 and $A$ is the number of valid grids with $N$ rows and $M$ columns.

• $1 \le T \le 50$
• $4 \le N, M \le 10$