一个字符串如果从左往右读和从右往左读都一样，那么这个字符串是一个回文串。例如："abcba"，"abccba"。

小明想通过添加字符把一个非回文字符串变成回文串。例如："trit"，可以添加一个'i' 变成回文串"tirit"。请你用程序计算出，对于一个给定的字符串，最少需要添加几个字符，才能变成回文串。

输入格式

输入一个长度为 $n(1≤n≤3000)$的字符串。（字符串只包含字母）

输出格式

输出最少需要添加的字符个数，占一行。

输出时每行末尾的多余空格，不影响答案正确性

要求使用「文件输入输出」的方式解题，输入文件为 palindrome.in，输出文件为 palindrome.out

样例输入

trit

样例输出

1