카지노

달리아는 ACPC 후원 모금팀의 부팀장이다. 올해는 상황이 나쁘다. 후원사가 턱없이 부족하다. 이대로면 참가 팀에게 풍선도 티셔츠도, 이름표조차 나눠 주지 못한다.

지금 와서 후원사를 구하기에는 늦었고 사실 무엇을 하기에도 늦었다는 것을 달리아도 안다. 그래도 포기하지 않고 도박에 걸어 보기로 했다. 근처 카지노가 새 게임을 막 내놓았는데, 그 게임이라면 승산이 있다고 본다.

규칙은 간단하다. 딜러가 테이블에 카드를 길게 늘어놓아 문자열 하나를 만들면, 달리아는 그 문자열에 들어 있는 팰린드롬 중 길이가 2 이상이면서 가장 긴 것을 모두 짚어내야 한다. 팰린드롬은 앞에서 읽으나 뒤에서 읽으나 같은 문자열이고, 가장 긴 팰린드롬은 그보다 긴 팰린드롬이 문자열 안에 없는 팰린드롬이다. 즉 문자열에 나타나는 팰린드롬의 최대 길이가 $X > 1$이면 길이가 $X$인 팰린드롬을 모두 출력한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 한 줄로 이루어지고, 비어 있지 않은 영어 소문자 문자열 $S$가 주어진다. $S$의 길이는 1000자 이하다.

각 테스트 케이스마다 먼저 Case #k: 꼴로 케이스 번호를 출력한다. $k$는 1부터 센다. 이어서 $S$에 나타나는 길이 $X$짜리 팰린드롬을 한 줄에 하나씩 출력한다. 여기서 $X$는 $S$에 나타나는 팰린드롬의 최대 길이다.

순서와 중복 규칙은 다음과 같다. 길이가 $X$인 팰린드롬이 나타나는 위치를 모두 찾은 다음, 시작 위치가 오른쪽에 있는 것부터 왼쪽으로 가면서 출력한다. 같은 문자열이 서로 다른 두 위치에 나타나면 두 번 출력한다.

$X = 1$이면, 즉 $S$에 길이가 2 이상인 팰린드롬이 하나도 없으면 케이스 번호 줄만 출력하고 팰린드롬은 출력하지 않는다.