#4263. 小C的打字机

内存限制:512 MiB 时间限制:2 Sec

题目描述

小C又搞到了一台搞笑的打字机。
这次,小C的打字机只能打出d和r两个字母。某个月高风黑的晚上,小Q突然过来现农,趁小C不注意打了一大堆乱七八糟的字符。等到小C发现时,小Q已经打进去N个字符了。
小C很郁闷,因为他的打字机非常奇葩——虽然可以任意输入,但是不能任意删除——每次只能删除一个长度为偶数的回文串的后半部分。
请帮小C求出经过若干次删除操作之后剩下的串的最短长度。

输入格式

一个字符串,表示小Q乱打的字符串,仅仅包含d,r两个字符。

输出格式

经过若干次删除操作之后剩下的串的最短长度。

样例

样例输入


			
drdrrrrrrd

样例输出


			
4

数据范围与提示

N<=10000