题目描述

给定一个由小写字母组成的字符串 $s$，你可以在字符串的任意位置插入任意字符。请计算将字符串 $s$ 变成回文串所需的最少插入次数。

回文串是指正读和反读都相同的字符串，例如 abba、abcba 都是回文串。

输入格式

第一行一个字符串 $s$，仅包含小写字母。

输出格式

输出一个整数，表示最少插入次数。

样例

abca

1

abcd

3

数据范围与提示

• $1 \le |s| \le 2000$
• 字符串仅包含小写字母