Паша и пароли
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Как-то раз Паша собрался покататься на велосипедах со своими друзьями - все таки ответить на вопрос, кто быстрее проедет город М. по кругу. После долгой изнурительной прогулки, в которой все ребята преодолели дистанцию за одинаковое время, каждый из $$$n$$$ человек хотел отдохнуть, но необходимо было решать проблему отсутствия победителя. И естественно, как и в любой спорной ситуации - ребята решили мериться своими паролями от любимой социальной сети. Довольно быстро найдя победителя, они задались вопросом: Как же выглядит пароль минимальной длины, который содержит все пароли ребят как непрерывные подстроки?

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

Input

В первой строке дано целое число $$$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$$$.

Output

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

Example

Input
3
3
abacaba
baba
saba
4
xzy
yyxx
yyy
xx
5
c
abcde
cde
bcde
cd
Output
sababacaba
yyyxxzy
abcde