Palindrome is a string that is identical to its reverse, like "level" or "aba". Given a string, find the longest palindrome in the string.
The input consists of multiple lines. Each line contains a string. The length of each string is no more than 1000.
case 1: the length of each string <= 50
case 2: the length of each string <= 100
case 3: the length of each string <= 500
case 4: the length of each string <= 1000
In each test case, output the longest palindrome in the string. If there are many palindromes of the same length, output the first one in the string.