题目描述

Pip has $N$ strings. Each string consists only of letters from A to Z. Pip would like to bundle their strings into groups of size $K$. Each string must belong to exactly one group.

The score of a group is equal to the length of the longest prefix shared by all the strings in that group. For example:

• The group {RAINBOW, RANK, RANDOM, RANK} has a score of $2$ (the longest prefix is 'RA').
• The group {FIRE, FIREBALL, FIREFIGHTER} has a score of $4$ (the longest prefix is 'FIRE').
• The group {ALLOCATION, PLATE, WORKOUT, BUNDLING} has a score of $0$ (the longest prefix is '').

Please help Pip bundle their strings into groups of size $K$, such that the sum of scores of the groups is maximized.

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case begins with a line containing the two integers $N$ and $K$. Then, $N$ lines follow, each containing one of Pip's strings.

输出格式

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum sum of scores possible.

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

提示

In Sample Case #1, Pip can achieve a total score of $0$ by making the groups:

• $\{\text{KICK}, \text{START}\}$, with a score of $0$.

In Sample Case #2, Pip can achieve a total score of $10$ by making the groups:

• $\{\text{G}, \text{G}\}$, with a score of $1$.
• $\{\text{GO}, \text{GO}\}$, with a score of $2$.
• $\{\text{GOO}, \text{GOO}\}$, with a score of $3$.
• $\{\text{GOOO}, \text{GOOO}\}$, with a score of $4$.

Limits

$1 \le T \le 100$.

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

$2 \le K \le N$.

$K$ divides $N$.

Each of Pip's strings contain at least one character.

Each string consists only of letters from A to Z.

Test Set 1

Each of Pip's strings contain at most $5$ characters.

Test Set 2

The total number of characters in Pip's strings across all test cases is at most $2 \times 10^6$.