Hamzawy

함자위(Hamzawy)는 프로그래밍 면접에서 아래 문제를 받았지만 답을 찾지 못했다. 대신 풀어 주자.

소문자 영어 알파벳으로 이루어진 문자열 $S$가 주어진다. $S$의 접두사이면서 $S$의 접미사이고, 동시에 $S$ 안에 부분문자열로 한 번 더 나타나는 문자열을 찾아야 한다. 이 세 번의 등장은 서로 겹치면 안 된다. 조건을 만족하는 문자열 중 가장 긴 것을 구하라.

문자열 $S$의 접두사는 $S$의 뒤에서 문자를 $0$개 이상 지워서 얻는 문자열이다. 접미사는 $S$의 앞에서 문자를 $0$개 이상 지워서 얻는 문자열이다. 부분문자열은 $S$의 앞에서 $0$개 이상, 뒤에서 $0$개 이상 지워서 얻는 문자열이다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 100$)

이어지는 $T$개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄은 소문자 영어 알파벳 'a'부터 'z'로만 이루어진, 비어 있지 않은 문자열 하나이며 길이는 $10^6$ 이하이다. 한 입력에 들어 있는 모든 문자열의 길이 합은 $10^6$ 이하이다.

각 테스트 케이스마다 한 줄에 Case n:을 출력하고, 공백 한 칸을 둔 다음 조건을 만족하는 가장 긴 문자열을 출력한다. $n$은 테스트 케이스 번호이고 $1$부터 시작한다. 조건을 만족하는 문자열이 없으면 문자열 자리에 -1을 출력한다.