시간 제한메모리 제한제출정답맞힌 사람정답 비율
20 초 (추가 시간 없음) 1024 MB64466.667%

## 문제

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, TT 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.

## 제한

• 1 ≤ T ≤ 100.
• 2 ≤ N ≤ 105.
• 2 ≤ K ≤ 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 (14점)

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

## Test Set 2 (21점)

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

## 예제 입력 1

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


## 예제 출력 1

Case #1: 0
Case #2: 10


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

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

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

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

## 예제 입력 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 6 by making the groups:

• {RAINBOW, RANK, RANDOM}, with a score of 2.
• {FIREBALL, FIREWALL, FIREFIGHTER}, with a score of 4.

## 채점 및 기타 정보

• 예제는 채점하지 않는다.