You are given a palindrome string of length consisting of only lowercase letters of the English alphabet. Find the shortest non-empty palindrome string such that concatenated with forms a palindrome. Formally, the string forms a palindrome.
输入格式
The first line of the input gives the number of test cases, . test cases follow. Each test case consists of lines. The first line of each test case contains an integer denoting the length of the string . The second line of each test case contains a palindrome string of length .
输出格式
For each test case, output one line containing Case #: , where is the test case number starting from and is the non-empty palindrome string as described above.
样例
样例输入 1
3
4
abba
4
cccc
6
cdccdc
样例输出 1
Case #1: abba
Case #2: c
Case #3: cdc
数据范围与提示
In Case , the shortest palindrome string is abba such that the concatenation is abbaabba, which is a palindrome.
In Case , the shortest palindrome string is c such that the concatenation is ccccc, which is a palindrome.
In Case , the shortest palindrome string is cdc such that the concatenation is cdccdccdc, which is a palindrome.
Limits
.
String is a palindrome consisting of only lowercase letters of the English alphabet.
