문자열 묶기

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는 가능한 점수 합의 최댓값이다.

• 1 ≤ T ≤ 100.
• 2 ≤ N ≤ 105.
• 2 ≤ K ≤ N.
• K는 N을 나눈다.
• Pip의 각 문자열은 적어도 하나의 문자를 포함한다.
• 각 문자열은 A부터 Z까지의 알파벳 대문자로만 이루어져 있다.