迴文自動機

題目敘述

卦長是一個迴文家，他寫出來的任何字串都會是迴文的形式。有天卦長發現世界上有太多字串不是迴文，不符合他的期望，所以他想請你打造一台迴文字動機，只要把字串輸入進去，他就可以在其中任意位置插入一些字符來讓它變成迴文，像是aab進入迴文字動機後會變成baab或aabaa...之類的迴文，但是每插一個字符，就會消耗你一單位的$SM$力，你要怎麼做才能讓消耗的$SM$力最小呢？

輸入說明

輸入有多行，每行有一個字串$S$

輸出說明

對於每個字串$S$輸出你最少要消耗幾單位的$SM$力才能讓它變成迴文

範例輸入

abcd
aaaa
abc
aab
abababaabababa
pqrsabcdpqrs

範例輸出

3
0
2
1
0
9

配分方法

• 0% 範例測資
• 40% $|S| \leq 100$
• 60% $|S| \leq 1000$

Hints

Judge Setting