题目描述

Pip 有 $N$ 个字符串。每个字符串仅由 A 到 Z 的字母组成。Pip 希望将这些字符串分成大小为 $K$ 的组。每个字符串必须恰好属于一个组。

一个组的得分等于该组中所有字符串共享的最长前缀的长度。例如：

• 组 {RAINBOW, RANK, RANDOM, RANK} 的得分为 $2$（最长前缀为 “RA”）。
• 组 {FIRE, FIREBALL, FIREFIGHTER} 的得分为 $4$（最长前缀为 “FIRE”）。
• 组 {ALLOCATION, PLATE, WORKOUT, BUNDLING} 的得分为 $0$（最长前缀为 “”）。

请帮助 Pip 将字符串分成大小为 $K$ 的组，使得各组得分之和最大。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $K$。随后 $N$ 行，每行包含 Pip 的一个字符串。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是可能的最大得分之和。

2
2 2
KICK
START
8 2
G
G
GO
GO
GOO
GOO
GOOO
GOOO

Case #1: 0
Case #2: 10

1
6 3
RAINBOW
FIREBALL
RANK
RANDOM
FIREWALL
FIREFIGHTER

Case #1: 6

提示

在样例 #1 中，Pip 可以通过以下分组获得总分 $0$：

• $\{\text{KICK}, \text{START}\}$，得分为 $0$。

在样例 #2 中，Pip 可以通过以下分组获得总分 $10$：

• $\{\text{G}, \text{G}\}$，得分为 $1$。
• $\{\text{GO}, \text{GO}\}$，得分为 $2$。
• $\{\text{GOO}, \text{GOO}\}$，得分为 $3$。
• $\{\text{GOOO}, \text{GOOO}\}$，得分为 $4$。

限制条件

$1 \le T \le 100$。

$2 \le N \le 10^5$。

$2 \le K \le N$。

$K$ 能整除 $N$。

Pip 的每个字符串至少包含一个字符。

每个字符串仅由 A 到 Z 的字母组成。

测试集 1

Pip 的每个字符串至多包含 $5$ 个字符。

测试集 2

所有测试用例中 Pip 的字符串的总字符数不超过 $2 \times 10^6$。

翻译由 DeepSeek V4 Pro 完成