Оптимальна клавіатура
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, +, *, /,?}.
Вихідні дані
Вихід містить один рядок на кожен тестовий випадок, що містить оптимальний рядок розрізу. Очевидно, що може бути більше одного оптимального рядка розрізу, тому виведіть оптимальний рядок розрізу, який є найменшим у лексикографічному порядку.