Как-то раз Паша собрался покататься на велосипедах со своими друзьями - все таки ответить на вопрос, кто быстрее проедет город М. по кругу. После долгой изнурительной прогулки, в которой все ребята преодолели дистанцию за одинаковое время, каждый из $$$n$$$ человек хотел отдохнуть, но необходимо было решать проблему отсутствия победителя. И естественно, как и в любой спорной ситуации - ребята решили мериться своими паролями от любимой социальной сети. Довольно быстро найдя победителя, они задались вопросом: Как же выглядит пароль минимальной длины, который содержит все пароли ребят как непрерывные подстроки?
Ребята справились с задачей довольно быстро, справитесь ли вы?
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 30$$$) — количество наборов входных данных.
Каждый набор входных данных описывается $$$n + 1$$$ строками.
В первой строке дано натуральное число $$$n$$$ ($$$1 \le n \le 17$$$) — количество друзей в компании.
Во оставшихся $$$n$$$ строках даны $$$n$$$ строк $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le |s_i| \le 5*10^4$$$) — пароли ребят от своих социальных сетей.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$30$$$.
В единственной строке выведите ответ - строку минимальной длины, содержащую в себе как непрерывные подстроки все пароли ребят.
33abacabababasaba4xzyyyxxyyyxx5cabcdecdebcdecd
sababacaba yyyxxzy abcde