palindrome

Chaque ligne correspond à un testcase. Un testcase contient une chaîne de [a-z] de longueur au plus 1000. Vous devez pour chaque testcase afficher sur une ligne le nombre minimum de lettres à insérer pour que la chaîne correspondante devienne un palindrome.

Votre algorithme doit être en O(n^2).

Input

abc
aab
aoob
abababaabababa
pqrsabcdpqrs
aaab
acaaaba
zzzaaazz
pooq

Télécharger l'entrée

Output

2
1
2
0
9
1
2
1
2

Télécharger la sortie

Il faut être logué pour pouvoir envoyer une soumission.