你是摇滚乐队“Denise and the Integers”的鼓手。你的鼓是一个圆柱体，上面包裹着一个矩形网格。

你的乐队计划在数学国（Mathland）演出。数学国的观众非常挑剔，他们要求鼓上的每个单元格都必须填入一个正整数；不允许填入零或负整数。此外，每个整数 $K$ 必须与恰好 $K$ 个填有相同整数的单元格相邻（共享一条边，而不仅仅是一个点）。也就是说，填有 $1$ 的单元格必须恰好与一个填有 $1$ 的单元格相邻，填有 $2$ 的单元格必须恰好与两个填有 $2$ 的单元格相邻，以此类推。除了这个限制外，单元格与其他什么数字相邻并不重要。（鼓的圆柱顶面和底面不计作单元格，也不需要装饰。注意，这意味着鼓顶行和底行的单元格每个只与三个其他单元格相邻，而所有其他单元格每个都与四个其他单元格相邻。）

例如，这是一个由 $3$ 行 $5$ 列网格构成的圆柱体的有效装饰：

你想知道有多少种不同的有效装饰方案。如果一种装饰不能通过旋转（绕圆柱体的对称轴）得到另一种，则认为这两种装饰是不同的。鼓的顶面和底面被视为不同，因此 $3 \times 5$ 网格的这种装饰与上面的装饰不同：

你的鼓有 $R$ 行和 $C$ 列。有多少种不同的有效装饰方案？结果可能很大，请输出装饰方案数对 $10^9 + 7$ ($1000000007$) 取模的结果。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 行，每行包含两个用空格分隔的整数 $R$ 和 $C$，分别表示鼓的行数和列数。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是如上所述的有效装饰方案数对 $10^9 + 7$ 取模的结果。

数据范围

$1 \le T \le 100$ $2 \le R \le 100$ $3 \le C \le 100$

样例

样例输入 1

2
2 4
3 5

样例输出 1

Case #1: 1
Case #2: 2

说明

在样例 $1$ 中，唯一的解是将所有单元格都填上 $3$。

在样例 $2$ 中，仅有的两个解是题目描述中展示的那两个。