Оптимальная клавиатура
Компания Optimus Mobiles производит мобильные телефоны, поддерживающие отправку SMS-сообщений. Телефоны оснащены клавиатурой с 12 клавишами, пронумерованными от 1 до 12. Каждой клавише соответствует строка символов. Чтобы ввести n-й символ из строки символов на определенной клавише, необходимо нажать на эту клавишу n раз. Optimus Mobiles стремится решить задачу распределения строк символов по клавишам так, чтобы при наборе случайного текста из словаря общих слов среднее количество нажатий клавиш было минимальным.
Более конкретно, рассмотрим набор символов {a, b, c, …, z, +, *, /, ?}, напечатанных на ленте, как показано на Рис. 2. Необходимо разрезать ленту на 12 частей, каждая из которых содержит один или несколько символов. 12 меток пронумерованы от 1 до 12 слева направо и будут назначены клавишам клавиатуры в этом порядке.
Рисунок 2
Вам необходимо написать программу, которая найдет 11 позиций разреза для данного словаря общих слов. Эти позиции должны минимизировать среднее количество нажатий клавиш для всех слов в словаре. Ваш вывод должен быть строкой из 11 символов, где символ i в этой строке является первым символом (i+1)-й метки.
Входные данные
Первая строка содержит одно целое число t (1 ≤ t ≤ 10), количество тестовых случаев. Каждый тестовый случай начинается со строки, содержащей целое число M (1 ≤ M ≤ 10000), количество общих слов в тестовом случае. В каждой из M последующих строк находится общее слово. Каждое слово содержит не более 30 символов из алфавита {a, b, c, …, z, +, *, /, ?}.
Выходные данные
Вывод должен содержать одну строку для каждого тестового случая, представляющую оптимальную строку разреза. Очевидно, может существовать более одной оптимальной строки разреза, поэтому выведите ту, которая является наименьшей в лексикографическом порядке.