Как известно, гараж Рика — его высокотехнологичный ассистент с искусственным интеллектом, умеющий выполнять довольно сложные задачи. Разумеется, получить доступ к управлению такой системой довольно сложно — придется обходить все слои защиты.
Но может быть вас удивит, что последний слой защиты — это $$$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$$$.
В единственной строке выведите ответ — строку минимальной длины, содержащую в себе как непрерывные подстроки все пароли в любом порядке. Если возможных вариантов ответа несколько, выведите любой из них.
33abacabababasaba4xzyyyxxyyyxx5cabcdecdebcdecd
sababacaba yyyxxzy abcde