题目描述

给定一个摆有棋子的棋盘，请计算在一步之内任意棋子能被吃掉的不同的方式总数。注意：在本题中，棋子可以被吃掉，而不考虑其颜色。

:::align{center} :::

例如，如果有 $3$ 个棋子：国王在 B2，兵在 A1，王后在 H8，那么总共能被吃掉的棋子数为 $3$。H8 的王后可以吃掉 B2 的国王，A1 的兵可以吃掉 B2 的国王，B2 的国王可以吃掉 A1 的兵。

棋盘上的位置表示为 A1, A2, ..., A8, B1, ..., H8。

棋子表示如下：

• (K) 国王：可以朝 $8$ 个方向移动一格。
• (Q) 王后：可以朝 $8$ 个方向移动任意格，但不能越过其他棋子。
• (R) 车：只能沿垂直或水平方向移动，但不能越过其他棋子。
• (B) 象：只能沿对角线移动，但不能越过其他棋子。
• (N) 马：可以移动到水平方向两格、垂直方向一格，或者水平方向一格、垂直方向两格的位置。
• (P) 兵：只能通过向斜前上方（朝向更大的数字，即 A → B，B → C，以此类推）移动来吃子。

输入格式

第一行输入给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例首先给出棋子的数量 $N$。随后 $N$ 行，每行给出一个棋子的位置，后跟连字符及棋子类型。

输出格式

对于每个测试用例，输出一行形如 Case #x: y 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是在一步之内任意棋子能被吃掉的不同的方式总数。

2
2
A1-K
A8-Q
3
B2-K
A1-P
H8-Q

Case #1: 1
Case #2: 3

提示

限制

$1 \le T \le 100$。

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

$1 \le N \le 10$。

棋子类型可包括 K、P。

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

$1 \le N \le 64$。

翻译由 DeepSeek V4 Pro 完成