回文串构造

题目描述

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

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

输入格式

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

输出格式

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

样例

样例输入 1

abca

样例输出 1

1

样例输入 2

abcd

样例输出 2

3

数据范围

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