题目描述

Siv 的生日在下周，Cel 正在为她准备生日礼物。因为 Siv 喜欢拼图，Cel 决定制作一个单词搜索谜题作为礼物。

在单词搜索谜题中，解题者会得到一个 $R$ 行 $C$ 列的矩形网格，解题者需要找出隐藏在网格中的所有有效单词。每个隐藏单词可以在网格中水平或垂直（但不能对角线）出现，可以是正向或反向。隐藏单词可以重叠。

Cel 有一个包含 $W$ 个不同单词的字典；这些单词是唯一可以隐藏在谜题网格中的单词。（当然，并非网格中每个连续的水平或垂直部分都必然包含某个隐藏单词。）这些单词不一定是真实的英语单词。每个单词可能在网格中出现一次或多次，也可能根本不出现。

Cel 已经创建好了单词搜索谜题。然而，问题在于：谜题太大，无法打印在一张纸上。由于 Siv 的生日即将到来，没有足够的时间从头创建一个新的单词搜索谜题。因此，Cel 想知道她是否可以通过简单地选择原始网格中的一个非空、与网格对齐的子网格来缩小网格尺寸。

随机选择一个子网格可能会导致谜题无聊，没有太多隐藏单词。因此，Cel 希望选择具有最大趣味值的子网格，其中子网格的趣味值定义为：

趣味值 = (匹配单词的总长度) / (子网格的宽度 + 子网格的高度)

注意：

• 单词必须完整地出现在子网格中才被计入。
• 如果一个单词在子网格中出现 $x$ 次，则其长度应在上述公式中累加 $x$ 次。
• 如果一个单词及其反向都在子网格中出现（即使在相同位置！），我们也会将这两次出现都计入。
• 具有最大趣味值的子网格可能就是整个原始网格。

你能帮助 Cel 找出子网格可能的最大趣味值，以及具有该趣味值的不同子网格的数量吗？两个子网格被认为是不同的，当且仅当存在网格中的某个格子（即某个 (行, 列) 位置）只属于其中一个子网格而不属于另一个。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的结构如下：

• 第一行包含三个整数 $R$、$C$ 和 $W$，含义如上所述。
• 接下来的 $R$ 行，每行恰好包含 $C$ 个大写英文字母。
• 接下来的 $W$ 行，每行恰好包含一个有效单词。每个单词只包含大写英文字母。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y/z n，其中：

• $x$ 是测试用例编号（从 $1$ 开始）。
• $y/z$ 是一个不可约分数，等于子网格的最大可能趣味值（如上所述）。
• $y$ 是一个非负整数。
• $z$ 是一个正整数。
• $n$ 是趣味值等于 $y/z$ 的子网格个数。

如果 $y$ 和 $z$ 的最大公约数为 $1$，则称 $y/z$ 为不可约分数。

2
1 2 1
AA
A
1 2 1
AA
B

Case #1: 8/3 1
Case #2: 0/1 3

2
1 3 2
ABC
ABC
CBA
4 4 1
AAAB
AAAB
AAAB
BBBB
AA

Case #1: 3/2 1
Case #2: 8/1 1

提示

记 $(i, j)$ 表示第 $i$ 行第 $j$ 列的格子。

在样例 #1 中，趣味值最高的子网格是整个网格。有效单词 A 在网格中出现 $8$ 次：

• 在格子 $(1, 1)$ 处水平方向出现 $2$ 次（正向一次，反向一次）。
• 在格子 $(1, 1)$ 处垂直方向出现 $2$ 次（正向一次，反向一次）。
• 在格子 $(1, 2)$ 处出现 $4$ 次（水平和垂直方向，正向和反向各一次）。

在样例 #2 中，有 $3$ 个子网格的趣味值等于 $0$：

• 仅包含一个格子 $(1, 1)$ 的子网格。
• 仅包含一个格子 $(1, 2)$ 的子网格。
• 左上角在 $(1, 1)$、右下角在 $(1, 2)$ 的子网格。

限制条件

• $1 \le T \le 100$。
• $1 \le R \le 100$。
• $1 \le C \le 100$。
• 有效单词列表中没有重复的单词。
• 有效单词列表中所有单词的总长度不超过 $5000$ 个字母。

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

• 每个有效单词的长度恰好为 $1$。
• $1 \le W \le 26$。

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

• $1 \le W \le 1000$。

翻译由 DeepSeek V4 Pro 完成