1737 - 最长回文
Description

所谓回文串就是正读和反读都一样的字符串。给定一个字符串，通过删除若干字符，都可以变成回文词。请计算最少删除多少字符才能够让给定的字符串变成回文。

Input

  • 一个字符串：表示给定的字符串 �s，保证 �s 完全由小写字母构成。


Output

  • 单个整数：表示最少删除多少字符可以让给定的字符串变成回文。


Examples

Input

ywczzc

Output

2

Input

aab

Output

1
Hint

记 �n 为输入字符串的长度，

  • 对 30%30% 的数据，1≤�≤201≤n≤20

  • 对 60%60% 的数据，1≤�≤5001≤n≤500

  • 对 100%100% 的数据，1≤�≤20001≤n≤2000


题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 1
通过次数 1
Stats
上一题
下一题