사슬 단어(Catenyms)

사슬 단어(catenym)는 마침표로 구분된 두 단어의 쌍으로, 첫 번째 단어의 마지막 글자가 두 번째 단어의 첫 글자와 같은 것을 말한다. 예를 들어 다음은 모두 사슬 단어이다.

dog.gopher
gopher.rat
rat.tiger
aloha.aloha
arachnid.dog

합성 사슬 단어(compound catenym)는 마침표로 구분된 세 개 이상의 단어의 나열로, 인접한 모든 단어 쌍이 각각 사슬 단어를 이루는 것이다. 예를 들면 다음과 같다.

aloha.aloha.arachnid.dog.gopher.rat.tiger

소문자 알파벳으로 이루어진 단어들의 사전이 주어질 때, 사전의 각 단어를 정확히 한 번씩 사용하는 합성 사슬 단어를 찾아라. 그러한 합성 사슬 단어가 여러 개이면 사전순으로 가장 앞서는 것을 출력하고, 존재하지 않으면 해가 없음을 알린다.

첫째 줄에 테스트 케이스의 개수 $t$가 주어진다. 각 테스트 케이스는 사전에 있는 단어의 개수 $n$ ($3 \le n \le 1000$)으로 시작한다. 이어서 서로 다른 $n$개의 단어가 한 줄에 하나씩 주어지며, 각 단어는 길이가 $1$ 이상 $20$ 이하인 소문자 알파벳 문자열이다.

각 테스트 케이스마다, 사전의 모든 단어를 정확히 한 번씩 사용하는 합성 사슬 단어 중 사전순으로 가장 앞서는 것을 한 줄에 출력한다. 그러한 합성 사슬 단어가 존재하지 않으면 대신 ***를 출력한다.