제곱 부분문자열

길이가 $2n$인 문자열 $T$의 길이 $n$인 접두사와 길이 $n$인 접미사가 같으면 $T$를 제곱 문자열이라고 한다. 빈 문자열은 제곱 문자열이다.

문자열 $S$가 주어질 때, $S$의 부분 문자열이면서 제곱 문자열인 가장 긴 문자열을 출력하라. $S$의 부분 문자열은 $S$에서 몇 개의 문자를 제거하고 나머지 문자들의 순서를 바꾸지 않은 문자열이다.

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다.

이후 $T$개의 줄에 각각 문자열 $S$가 주어진다. $S$는 알파벳 소문자로만 이루어져 있다.

각 문자열의 길이는 1 이상 3000 이하이며, 주어지는 모든 문자열의 길이 합은 3000 이하이다.

각 테스트 케이스에 대해 다음과 같이 출력하라.

정답이 빈 문자열이면 Case #T: 0을 한 줄에 출력한다.

정답이 빈 문자열이 아니면 Case #T: L을 첫 줄에 출력하고, 다음 줄에 정답을 출력한다.

여기서 $T$는 테스트 케이스의 번호(1부터 시작)이고, $L$은 정답 문자열의 길이이다.