Description

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

• 这些格子连成一块。从 $s$ 中的任意一个格子出发，只通过 $s$ 内的相邻格子可以到达 $s$ 中的任意一个格子。
• 恰好有两个格子在 $s$ 中只有一个相邻格子（即“端点”）。
• $s$ 中的其他每个格子都有恰好两个相邻格子。

例如，下图中，第一个网格是合法的，而第二个网格不是——虽然黑色格子构成了一条路径，但白色格子没有。

给定 $N$ 和 $M$，计算合法网格的数量。注意，对称性不影响结果——只要两个合法网格在某个位置不同，即使一个可以通过旋转或翻转变为另一个，也认为它们是不同的。

Input Format

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

Output Format

对于每个测试用例，输出一行，格式为 “Case #$x$: $A$”，其中 $x$ 是测试用例编号（从 1 开始），$A$ 是指定大小网格的合法方案数。

3
4 4
4 6
5 5

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

Hint

数据范围

• $1 \leq T \leq 50$

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

• 时间限制：30 15 秒每组数据。
• $4 \leq N, M \leq 10$

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

• 时间限制：120 60 秒每组数据。
• 对于 80% 的测试用例，$4 \leq N, M \leq 50$
• 对于 90% 的测试用例，$4 \leq N, M \leq 70$
• 对于所有测试用例，$4 \leq N, M \leq 100$

由 ChatGPT 4.1 翻译