Ahmed Samir Hamza (Hamzawy, a world finalist in the 2013 ICPC in St. Petersburg, a judge in the TCPC and an IBM software engineer), was in a programming interview lately and got asked a puzzling question that he could not answer, so he has asked you to help him to solve it.</p>

Here is the question, given a string S of lowercase English characters, find a string which is a prefix of S, a suffix of S and a substring in S. The three occurrences of this string must not overlap. You should find the longest string which satisfies the above conditions.

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

입력 형식

Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 100). Followed by T lines, each test case is a single line containing a non-empty string of lowercase English characters (from ‘a’ to ‘z’) containing no more than 106 characters.

출력 형식

For each test case print a single line containing “Case n:” (without the quotes) where n is the test case number (starting from 1) followed by a space then the longest required string, if there is no such string, print -1 instead.

예제 입력

2
barbararhubar
barbararhuaar

예제 출력

Case 1: bar
Case 2: -1