题目描述

给定一个字符串 $S$，你可以在任意位置插入任意字符。求把 $S$ 变成回文串最少需要插入多少个字符。

（等价于：$|S|-\text{LPS}(S)$，其中 LPS 为最长回文子序列长度。）

输入格式

一行一个字符串，长度不超过 1000，仅含小写英文字母。

输出格式

一个整数，最少插入次数。

样例输入 #1

abzdb

样例输出 #1

2

样例输入 #2

abcba

样例输出 #2

0

数据范围

$1\le |S|\le 1000$。