Гараж
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как известно, гараж Рика — его высокотехнологичный ассистент с искусственным интеллектом, умеющий выполнять довольно сложные задачи. Разумеется, получить доступ к управлению такой системой довольно сложно — придется обходить все слои защиты.

Но может быть вас удивит, что последний слой защиты — это $$$n$$$ обычных мастер-паролей в виде строк, где $$$i$$$-й пароль служит для получения доступа к управлению $$$i$$$-м сервисом гаража. Рика не сильно интересовала безопасность на таком глубоком уровне, ведь кто вообще, кроме него, может взломать все предыдущие слои защиты?

Но сегодня от скуки он задумался, а какая минимальная по длине строка подойдет в качестве мастер-пароля от всех возможностей гаража? Чтобы строка подходила в качестве единого мастер-пароля, она должна содержать все $$$n$$$ мастер-паролей в качестве непрерывных подстрок в любом порядке.

Разумеется, Рик уже справился с тем, чтобы найти минимальный по длине единый мастер-пароль, но может быть вы справитесь быстрее?

Входные данные

В первой строке дано целое число $$$t$$$ — количество реальностей, в которых Рик задумался о безопасности ($$$1 \le t \le 30$$$). Далее следуют $$$t$$$ наборов входных данных, каждый набор входных данных описывается $$$n + 1$$$ строками.

В первой строке набора входных данных дано целое число $$$n$$$ — количество устройств в гараже, имеющих мастер-пароль ($$$1 \le n \le 17$$$).

Во $$$i$$$-й из следующих $$$n$$$ строк дана строка $$$s_i$$$ — мастер-пароль от $$$i$$$-го сервиса гаража ($$$1 \le |s_i| \le 5 \cdot 10^4$$$). Пароли состоят из маленьких букв латинского алфавита от 'a' до 'z'.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$30$$$.

Выходные данные

В единственной строке выведите ответ — строку минимальной длины, содержащую в себе как непрерывные подстроки все пароли в любом порядке. Если возможных вариантов ответа несколько, выведите любой из них.

Пример

Входные данные
3
3
abacaba
baba
saba
4
xzy
yyxx
yyy
xx
5
c
abcde
cde
bcde
cd
Выходные данные
sababacaba
yyyxxzy
abcde