描述

$Optimus$ $Mobiles$ 生产支持 $SMS$ 消息的手机。移动设备有一个由 $12$ 个键组成的键盘，编号为 $1$ 到 $12$。每个键都有一个字符串。要键入特定键的字符串中的第 $n$ 个字符，应按该键 $n$ 次。$Optimus$ $Mobiles$ 希望解决将字符串分配给键的问题，以便从常用词词典中输入随机文本时，平均输入工作量（即平均击键次数）是最小的。

图 1

更准确地说，考虑一组字符 {$a， b， c,..., z， +， *， /， ？$} 印在标签带上，如图 $2$ 所示。我们想将磁带剪成 $12$ 块，每块包含一个或多个字符。这 $12$ 个标签从左到右编号为 $1$ 到 $12$，并将按此顺序分配给键盘键。

图 2

您将编写一个程序来查找给定常用词词典的 $11$ 个切割位置。剪切位置应最小化字典中所有常用单词的平均击键次数。您的输出应是一个包含 $11$ 个字符的字符串，其中此字符串中的字符 $i$ 是 $（i+1）$ 的第一个字符$th$标签。

输入

第一行包含一个整数 $t$ $（1 <= t <= 10）$，即测试用例的数量。每个测试用例都以一行开头，其中包含一个整数 $M$ $（1 <= M <= 10000）$，即测试用例中常用字的数量。在后面的每一行 $M$ 中，都有一个通用词。每个常用单词最多包含字母 {$a， b， c,..., z， +， *， /， ？$} 中的 $30$ 个字符。

输出

输出包含每个测试用例的一行，其中包含一个最佳剪切字符串。显然，可能有多个最佳剪切字符串，因此请打印最佳剪切字符串，它是按字典顺序排列的最小字符串。

输入数据$1$

2

2

hi

ok

5

hello

bye

how

when

who

输出数据$1$

bcdefghijko

bcdefhlnowy

来源 德黑兰 $2003$ $[Tehran]$