The Paths of Yin Yang (Large)

You are given a grid with $N$ rows and $M$ columns. Each cell is painted black (yin) or white (yang). Two cells are neighbors when they share an edge of unit length. The grid is valid when the black cells form one path and the white cells form one path. A set $S$ of cells is a path when all three of the following hold.

• $S$ is connected. From any cell of $S$ you reach every other cell of $S$ by moving between neighbors inside $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 one is not: its black cells form a path, but its white cells do not.

Given $N$ and $M$, count the valid grids. Two valid grids that differ in at least one cell are counted separately, 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 of the given size.

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