최적의 키패드

휴대폰에는 $1$번부터 $12$번까지 번호가 매겨진 12개의 키로 이루어진 키패드가 있습니다. 각 키에는 문자열이 하나씩 배정되어 있으며, 어떤 키에 배정된 문자열의 $n$번째 문자를 입력하려면 그 키를 $n$번 눌러야 합니다. 자주 쓰이는 단어들의 사전이 주어졌을 때, 이 단어들을 입력하는 데 드는 평균 타수(키를 누르는 횟수)가 최소가 되도록 각 키에 문자열을 배정하는 것이 목표입니다.

그림 1

30개의 문자 $\{a, b, c, \dots, z, +, *, /, ?\}$ 가 이 순서 그대로 라벨 테이프 위에 적혀 있다고 합시다. 이 테이프를, 각 조각이 하나 이상의 연속된 문자를 담도록 12개의 비어 있지 않은 조각으로 자릅니다. 왼쪽부터 각 조각(라벨)에 $1$번부터 $12$번까지 번호를 붙이고, $k$번 라벨을 $k$번 키에 배정합니다. 한 라벨 안에서 첫 번째 문자는 $1$타, 두 번째 문자는 $2$타가 들며, 일반적으로 $n$번째 문자는 $n$타가 듭니다.

그림 2

주어진 사전에 대해, 모든 단어를 입력하는 데 필요한 전체 타수를 최소로 만드는 11개의 자르는 위치를 고르십시오(이는 단어당 평균 타수를 최소로 만드는 것과 같습니다). 답은 11개의 문자로 이루어진 문자열로 나타내며, 이 문자열의 $i$번째 문자는 $i+1$번 라벨의 첫 번째 문자입니다. $1$번 라벨의 첫 번째 문자는 항상 $a$이므로 생략합니다.

첫째 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 10$)가 주어집니다. 각 테스트 케이스의 첫 줄에는 자주 쓰이는 단어의 개수 $M$ ($1 \le M \le 10000$)이 주어집니다. 이어지는 $M$개의 줄에는 각각 단어가 하나씩 주어집니다. 각 단어는 알파벳 $\{a, b, c, \dots, z, +, *, /, ?\}$ 에 속하는 문자로만 이루어지며 길이는 최대 30입니다.

각 테스트 케이스마다, 최적의 자르기 문자열을 한 줄에 출력합니다. 최적의 자르기 문자열이 여러 개일 수 있으므로, 그중 사전순으로 가장 앞서는 것을 출력합니다.