Square Substring

A string $T$ of length $2n$ is called a square string if its prefix of length $n$ and its suffix of length $n$ are equal. The empty string is a square string.

Given a string $S$, print the longest string that is both a substring of $S$ and a square string. A substring of $S$ is a string obtained by removing some characters from $S$ without changing the order of the remaining characters.

The first line contains the number of test cases $T$.

Each of the next $T$ lines contains a string $S$. $S$ consists only of lowercase English letters.

The length of each string is between 1 and 3000, inclusive. The total length of all given strings is at most 3000.

For each test case, print the answer as follows.

If the answer is the empty string, print Case #T: 0 on one line.

If the answer is not the empty string, print Case #T: L on the first line, and print the answer on the next line.

Here $T$ is the test case number (starting from 1), and $L$ is the length of the answer.