DNA 실험실

사악한 박사가 자신만의 DNA 실험실을 막 짓기 시작했지만 아직 최신 기술을 따라잡지 못했다. 그는 자신의 DNA를 추출하고 개량하여 스스로를 복제하려 한다. 혈액 세포에서 DNA를 추출하는 방법은 이미 알아냈지만, DNA 서열을 읽으려면 DNA를 여러 개의 짧은 조각으로 잘라 각 조각을 따로 분석해야 한다. 그는 이 조각들을 원래 서열로 다시 합치는 방법을 몰라, 똑똑한 학생 몇 명을 납치해 문제를 대신 풀게 했다. 당신도 그중 한 명이다.

알파벳 A(아데닌), C(사이토신), G(구아닌), T(타이민)로 이루어진 문자열들의 목록이 주어진다. 주어진 모든 문자열을 부분 문자열로 포함하는 가장 짧은 문자열을 구하라. 그러한 가장 짧은 길이의 문자열이 여러 개라면 사전순으로 가장 앞서는 것을 출력하라.

첫째 줄에 시나리오의 개수가 주어진다.

각 시나리오의 첫째 줄에는 문자열의 개수 $n$이 주어진다 ($1 \le n \le 15$). 이어서 $n$개의 줄에 문자열이 한 줄에 하나씩 주어진다. 각 문자열의 길이는 $1$ 이상 $100$ 이하이며, 문자 A, C, G, T로만 이루어져 있다.

각 시나리오마다 먼저 Scenario #i:를 출력한다. 여기서 $i$는 $1$부터 시작하는 시나리오 번호이다. 그다음 줄에 해당 시나리오의 모든 문자열을 부분 문자열로 포함하는 가장 짧은 문자열을 출력한다. 그러한 문자열이 여러 개라면 사전순으로 가장 앞서는 것을 출력한다. 연속한 시나리오 사이는 빈 줄로 구분한다.