도시 합병

정보통신 기술의 발전으로 더 넓은 지역에 더 빠르고 더 적은 비용으로 행정 서비스를 제공할 수 있게 되었다. 이에 자극받아, 또 부족한 재정을 아끼기 위해 여러 도시의 시장들이 도시 합병을 논의하기 시작했다.

물론 실제로 합병을 진행하는 데에는 여러 장애물이 있다. 각 도시는 시민들이 자랑스러워하는 고유의 문화를 가지고 있다. 가장 큰 갈등의 원인 중 하나는 새 도시의 이름이다. 모든 시민은 새 도시의 이름에 적어도 자기 도시의 원래 이름이 부분으로 포함되어야 한다고 주장한다. 그러나 원래 이름을 모두 단순히 이어 붙이면 일상적으로 쓰기에 이름이 너무 길어진다.

당신은 시장들의 요청으로, 합병되는 모든 도시의 원래 이름을 포함하는 가장 짧은 새 도시 이름을 찾는 프로그램을 작성해야 한다. 두 개 이상의 이름이 공통 부분을 가지면 그 부분을 겹쳐서 쓸 수 있다. 예를 들어 "FUKUOKA", "OKAYAMA", "YAMAGUCHI" 세 도시를 합병한다면, "FUKUOKAYAMAGUCHI"는 세 원래 이름을 모두 포함하는 이름이다. 이 이름은 "FUKUYAMA"의 모든 글자를 순서대로 포함하지만 연속된 부분 문자열로 나타나지는 않으므로, "FUKUYAMA"가 포함되었다고 보지는 않는다.

어떤 원래 이름이 포함된다는 것은 반드시 연속된 부분 문자열로 나타나는 경우만을 뜻한다.

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋의 첫 줄에는 합병할 도시의 수를 나타내는 양의 정수 $n$ ($n \le 14$)이 주어진다. 이어지는 $n$개의 줄에는 각 도시의 이름이 한 줄에 하나씩 대문자 알파벳으로 주어진다. 어떤 도시 이름도 20자를 넘지 않으며, 서로 같은 이름을 가진 도시는 없다.

입력의 끝은 $0$ 하나만 있는 줄로 표시된다.

각 데이터셋마다 새 도시 이름의 가능한 가장 짧은 길이를 한 줄에 출력한다. 그 외의 다른 문자는 출력하지 않는다.