题目描述

回文串是一种正读和反读都相同的字符串。给定一个字符串，你可以在任意位置插入若干个字符，使其变为回文串。求最少需要插入多少个字符。

例如 $\verb!Ab3bd!$ 插入 $2$ 个字符后可以变成回文串 $\verb!dAb3bAd!$ 或 $\verb!Adb3bdA!$，但插入少于 $2$ 个字符无法变成回文串。

注意：此问题区分大小写。

输入格式

输入共一行，一个非空字符串。

输出格式

输出一个整数，即最少需要插入的字符数。

样例

Ab3bd

2

提示

记字符串长度为 $l$。

对于全部数据，$0 \lt l \le 1000$。字符串由大小写字母和数字组成。