Hamzawy

Hamzawy was asked the following question in a programming interview and could not answer it, so solve it for him.

You are given a string $S$ of lowercase English letters. Find a string that is a prefix of $S$, is a suffix of $S$, and also appears once more as a substring of $S$. The three occurrences must not overlap. Print the longest string that satisfies these conditions.

A prefix of a string $S$ is a string obtained by deleting zero or more characters from the end of $S$. A suffix is a string obtained by deleting zero or more characters from the start of $S$. A substring is a string obtained by deleting zero or more characters from the start of $S$ and zero or more characters from the end of $S$.

The first line contains the number of test cases $T$. ($1 \le T \le 100$)

Each of the next $T$ lines holds one test case: a non-empty string of lowercase English letters 'a' to 'z' whose length is at most $10^6$. The sum of the lengths of all strings in one input is at most $10^6$.

For each test case print one line containing Case n:, then a single space, then the longest string that satisfies the conditions. Here $n$ is the test case number, starting from $1$. If no such string exists, print -1 in place of the string.