Casino

Dalia is the assistant director of the fundraising team at the ACPC. This year is going badly. Sponsors are nowhere near enough. If nothing changes, the teams get no balloons, no T-shirts, not even name tags.

Dalia knows that signing a sponsor now is too late, and that doing anything at all is too late. She does not give up. She decides to gamble instead. A casino nearby has just introduced a new game, and she thinks she has a real chance at it.

The rules are simple. The dealer lays out a long row of cards on the table that spells one string, and Dalia has to point out every palindrome in that string that has length 2 or more and is as long as possible. A palindrome reads the same forward and backward, and a maximum length palindrome is one that no longer palindrome in the string beats. So if the maximum palindrome length in the string is $X > 1$, print every palindrome of length $X$ in the string.

The first line contains the number of test cases $T$. Each test case is one line holding a non-empty string $S$ of lowercase English letters. The length of $S$ is at most 1000.

For each test case, first print the case number in the form Case #k:, where $k$ counts from 1. Then print the palindromes of length $X$ that occur in $S$, one per line, where $X$ is the maximum palindrome length in $S$.

Order and duplicates work like this. Find every position where a palindrome of length $X$ occurs, then print those occurrences by starting position, rightmost first and moving left. If the same string occurs at two different positions, print it twice.

If $X = 1$, that is, if $S$ contains no palindrome of length 2 or more, print only the case number line and no palindrome.