A Subsequence is a sequence obtained by deleting zero or more characters in a string. A Palindrome is a string which when read from left to right, reads same as when read from right to left. Given a string, find the longest palindromic subsequence. If there are many answers to it, print the lexicographically smallest.

Input

Consists of several tests, each in a separate line. Maximum length of a line is 1000. Each line contains characters from 'a' to 'z' only.

Output

For each line print the lexicographically smallest longest palindromic subsequence.