故，有与无生于彼此； 难与易成于彼此； 长与短形于彼此； 高与下盈于彼此； 音与声和于彼此； 前与后随于彼此。 ——《道德经》，老子，周朝，中国古代。 （由本人意译。）

题目描述

给定一个 $N$ 行 $M$ 列的矩形网格，每个单元格可以被标记为黑色（阴）或白色（阳）。如果两个单元格共享一条单位长度的边，则称它们为邻居。如果所有黑色单元格构成一条路径，且所有白色单元格也构成一条路径，则称该网格是有效的。路径是指满足以下条件的单元格集合 $S$：

• 这些单元格构成一个连通块。从 $S$ 中的任意单元格出发，可以通过 $S$ 内部的邻居移动到达 $S$ 中的任何其他单元格。
• $S$ 中恰好有两个单元格在 $S$ 中各只有一个邻居。这两个单元格被称为路径的“端点”。
• $S$ 中的其余每个单元格在 $S$ 中都有且仅有两个邻居。

例如，在下图中，第一个网格是有效的，而第二个网格不是——尽管黑色单元格构成了一条路径，但白色单元格并没有构成路径。

给定 $N$ 和 $M$，计算有效网格的数量。注意，对称性不予考虑——只要两个有效网格在某个位置不同，它们就被视为不同的网格，即使其中一个可以通过旋转或翻转得到另一个。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来的 $T$ 行，每行包含两个由空格分隔的整数 "$N\ M$"，含义如上所述。

输出格式

对于每个测试用例，输出一行格式为 "Case #$x$: $A$" 的内容，其中 $x$ 是从 1 开始的用例编号，$A$ 是指定大小的有效网格数量。

数据范围

内存限制：1GB。

$1 \le T \le 50$

小数据集（测试集 1 - 可见；17 分）

时间限制：每个测试集 5 秒。

$4 \le N, M \le 10$

大数据集（测试集 2 - 隐藏；35 分）

时间限制：每个测试集 30 秒。

对于 80% 的测试用例，$4 \le N, M \le 50$

对于 90% 的测试用例，$4 \le N, M \le 70$

对于所有测试用例，$4 \le N, M \le 100$

样例

输入 1

3
4 4
4 6
5 5

输出 1

Case #1: 24
Case #2: 44
Case #3: 48