Blue Jeans

Genographic Project는 IBM과 내셔널 지오그래픽 협회(The National Geographic Society)가 함께 진행하는 연구 프로젝트로, 수십만 명의 기증자로부터 얻은 DNA를 분석하여 인류가 지구에 어떻게 퍼져 나갔는지를 지도로 그리는 것을 목표로 한다.

IBM 연구원인 당신은 주어진 여러 DNA 조각에서 공통으로 나타나는 부분을 찾아, 이를 설문 정보와 연관지어 새로운 유전 표지를 식별하는 프로그램을 작성해야 한다.

DNA 염기 서열은 분자에서 염기가 나타나는 순서대로 나열하여 표기한다. 염기는 아데닌(A), 티민(T), 구아닌(G), 사이토신(C)의 네 종류가 있다. 예를 들어 6개의 염기로 이루어진 DNA 서열은 TAGACC처럼 나타낼 수 있다.

여러 개의 DNA 염기 서열이 주어졌을 때, 모든 서열에 공통으로 등장하는 가장 긴 연속된 염기 구간(연속 부분 문자열)을 구하라.

입력의 첫 줄에는 데이터셋의 개수를 나타내는 정수 $n$이 주어진다. 각 데이터셋은 다음과 같이 구성된다.

1. 이 데이터셋에 포함된 염기 서열의 개수를 나타내는 양의 정수 $m$ ($2 \le m \le 10$).
2. 이어지는 $m$개의 줄에는 각각 60개의 염기로 이루어진 염기 서열이 한 줄에 하나씩 주어진다.

각 데이터셋마다, 주어진 모든 염기 서열에 공통으로 나타나는 가장 긴 연속 부분 문자열을 출력한다. 이 최장 공통 부분 문자열의 길이가 3보다 짧으면 대신 no significant commonalities 를 출력한다. 같은 최대 길이를 가지는 부분 문자열이 여러 개라면, 사전순으로 가장 앞서는 것 하나만 출력한다.