You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[丛雨]有一个字符串，她想知道最少插入多少字符使得它变成一个回文串。

输入格式(palind.in)

一行一个字符串。

输出格式(palind.out)

一行一个正整数，表示最少插入的字符数量。

输入样例

helloworld

输出样例

5

数据范围

对于 $100\%$ 的数据，保证 $1 \le 字符串长度 \le 1000$ ，字符串全由小写字母构成。