RM Contest 03

One day little girl Lilith was playing with strings. She made a string X which is a palindrome! Suddenly her favorite dog “hehway” came and ate some of the characters from X but not all! Lilith built another palindrome but naughty “hehway” came again and destroyed it! Watching this happening again and again Lilith’s boyfriend Mada thought that he can give her a machine as birthday present that automatically converts any string to palindrome by adding some characters. The machine will be connected with an infinite supply of lowercase Latin characters (‘a’-’z’).

The machine also has two amazing features:

1. The machine always adds minimum number of characters to the input string in order to convert it to a palindrome.
2. If there are multiple ways then it always produces the lexicographically smallest palindrome.

We all know that machines are not perfect! So, there is no way to guaranty that the machine generated palindrome is the original palindrome that Lilith made in the first place! But, “Mada” thought that it will at least help Lilith to forget the sorrow of losing her favorite palindromes to her favorite dog!

So, when you enter a string X into the machine, the machine’s output looks like N Y, where N is number of new characters that it added to X to make Y. And Y is the lexicographically minimum palindrome produced by adding 0 or more characters with X.

Can you help “Mada” with the algorithm of the machine?

Input:

The first line of input determines the number of test cases (1<=T<=2000). Each of the next T lines contains a string S (1<=|s|<=100). S is a string which is left after Lilith’s dog “hehway” ate some of the characters (possibly none!) of the original string. S will be the input of the machine.

Output:

Print the machine’s output in each line along with the case number! See Sample test cases for I/O format and explanation for more clarification about the problem.

Sample:

Input:
4
ab
aba
abcd
bca

Output:
Case 1: 1 aba
Case 2: 0 aba
Case 3: 3 abcdcba
Case 4: 2 abcba

Explanation:

First input “ab” => We can add a "b" to its beginning which will make it “bab” we can also add an "a" to its end which till make it “aba”. In either way we are adding one extra character but “aba” is lexicographically smaller than “bab”. So our result is “aba”. We can also add “ba” to the end of “ab” which will result into “abba” which is also a palindrome, but in that case we would need two characters instead of one. We need to ensure minimal character insertion at first and then try to minimize the result lexicographically. See this way, (a) + ab + (ba + a) results into “aabbaa” which is lexicographically smaller than “aba” but it needs 4 characters to build that palindrome where “aba” needs only 1. So, “aba” is the desired result!

In second case the string is already a palindrome!

Look at the fourth case. We are allowed to add character at any position of the given string not only just at beginning or end!