What is the Problem?
A palindrome is a word that has the exact same sequence of letters whether you read it left to right or right to left. The words “noon” and “radar” are palindromes. The words “noob” and “palindrome” are not.
Patty loves palindromes. She finds them soothing. Patty knows that you can turn any word into a palindrome by adding letters to the left and/or the right. For example, you can turn “ECOO” into “OOCECOO” or “ECOOCE” or even “DOOCECOOD”. Patty loves palindromes so much that any time she sees a word written down somewhere, she immediately converts it to a palindrome in her head.
DATA11.txt (DATA12.txt for the second try) will contain 10 test cases. Each test case consists of a single line containing a string of lowercase letters of maximum length 1 000 000. Your code should output the minimum number of letters Patty would need to add to the left and/or the right in order to convert the string to a palindrome.
Note that the sample input below contains only 3 test cases but the data files will contain 10.
Sample Input
ecoo
impala
anagram
Sample Output
2
3
4