A palindrome is a word that has the exact same sequence of letters when read forwards or backwards. The words noon and radar are palindromes, whereas the words noob and palindrome are not.

Patty loves palindromes, as she finds them soothing. Patty knows that you can turn any word into a palindrome by adding letters to the left and / or 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.

The input will contain \(10\) test cases. Each test case consists of a single line containing a string of lowercase characters of maximum length of \(10^6\). 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 actual data files will contain \(10\).

Sample Input

ecoo
impala
anagram

Sample Output

2
3
4

Question Development Team

Sam Scott (Sheridan College)
Kevin Forest (Sheridan College)
Stella Lau (University of Cambridge)
Reyno Tilikaynen (University of Waterloo)
John Ketelaars (ECOO-CS Communications)
David Stermole (ECOO-CS President)

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org