#216752. [GKS 2020 #A] Bundling

Pip has strings. Each string consists only of letters from A to Z. Pip would like to bundle their strings into groups of size . 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 (the longest prefix is 'RA').
• The group {FIRE, FIREBALL, FIREFIGHTER} has a score of (the longest prefix is 'FIRE').
• The group {ALLOCATION, PLATE, WORKOUT, BUNDLING} has a score of (the longest prefix is '').

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

The first line of the input gives the number of test cases, . test cases follow. Each test case begins with a line containing the two integers and . Then, 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.

样例输入 1

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

样例输出 1

Case #1: 0
Case #2: 10

样例输入 2

1
6 3
RAINBOW
FIREBALL
RANK
RANDOM
FIREWALL
FIREFIGHTER

样例输出 2

Case #1: 6

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

• , with a score of .

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

• , with a score of .
• , with a score of .
• , with a score of .
• , with a score of .

Limits

.

.

.

divides .

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 characters.

Test Set 2

The total number of characters in Pip's strings across all test cases is at most .