| 描述 |
|---|
众所周知ovo非常喜欢"dp"这个组合，某一天他得到了一个字符串s，他可以每次花费一点理智把'd'变成'p'或者把'p'变成'd'，从而使得这个字符串变成前半段都是'd'，后半段都是'p'的字符串 "ddddppp","dpppp","dp" 是合法的 "dpd","ddd","pppddd" 是不合法的 但是ovo希望自己足够理智，所以想要知道能够使得字符串合法的最小理智花费。 |
| 输入 |
T组样例 每组样例一行字符串s |
| 输出 |
| 针对每组样例输出最小理智花费 |
| 样例输入 |
3 ddddp pdpdp ppppp |
| 样例输出 |
0 2 1 |
| HINT |
针对40%的样例，length(s) <= 100 针对60%的样例，length(s) <= 1000 针对100%的样例，length(s) <= 100000 针对100%的样例，2 <= length(s) 且 所有样例的字符串长度总和不超过 1e6 |
| 来源 |
| TKK-ICPC Round#9 |