A palindrome is a word that is spelt the same backwards or forwards. Examples are ”level” and ”madam”. An anagram is a word made from another word just by rearranging the characters, like ”made” to ”dame”. For this problem anagrams and palindromes may not be valid English words. For example ”daamm” is an anagram of ”madam” and ”amdma” is also palindrome although it is not an English word. ”daamm” is also called a palinagram because it is the anagram of a palindrome. Any palindrome is also a palinagram but the vice versa is not always true. Some other examples palinagrams are ”aabbcc”, ”aaaaa” etc. Given a string you will have to print the string that needs to be appended with it to make it a palinagram. Input The input file contains at most 6000 test cases. The description of each test case is given below. Each case consists of a single string S of length L (1 ≤ L ≤ 500). This string contains only lowercase English letters (‘a’ to ‘z’). Input is terminated by a line containing a single hash (‘#’) character. This line need not be processed. Output For each line of input produce one line of output. The line contains the string that needs to be appended to the given string to make it a palinagram (Can be an empty string as well). If there are more than one solutions output the shortest one, if there is still a tie output the lexicographically smallest one. Sample Input ddc aaab # Sample Output a