306022 - 删最少字符使区间回文

给定一个字符串,每次可以删除任意一个字符,求将该字符串变为回文串的最少删除次数。

Input

一行字符串(长度 ≤ 500)。

Output

一个整数,表示最少删除次数。

Examples

Input

abcda

Output

2
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题