Johnny 正在和他的朋友 Bob 玩“石头、剪刀、布”游戏。游戏由若干轮组成，每轮中双方同时出示石头、剪刀或布。出示更强符号的玩家赢得该轮；如果双方出示相同的符号，则该轮平局。符号的强弱规则如下： 剪刀切布（剪刀强于布）， 布包石头（布强于石头）， * 石头砸剪刀（石头强于剪刀）。

赢得更多轮次的玩家赢得整场比赛。

掌握这个游戏是 Bob 人生中唯一的目标。经过多年的训练，他准备了一长串他认为的最佳策略序列并将其背了下来。Johnny 无意中发现了这份序列的打印件，于是决定捉弄 Bob：他想要赢得比赛（即赢得的轮次严格多于 Bob），并且他想以“史诗般”的方式获胜。当 Johnny 改变他出示符号的次数最少时，这次胜利就是“史诗般”的。距离比赛开始没多少时间了，Johnny 仍然不知道他需要做出的最少改变次数是多少。请帮他计算出来。

输入格式

输入的第一行也是唯一一行包含一个长度不超过 $10^6$ 的字符串，其中第 $i$ 个位置的字母表示 Bob 在第 $i$ 轮中出示的符号。每个字母为 K、P 或 N，分别代表石头、布和剪刀。

输出格式

输出的第一行也是唯一一行应包含一个整数：Johnny 为了赢得比赛所需改变出示符号的最少次数。

样例

输入 1

KPNPKP

输出 1

0

Johnny 可以在不做任何改变的情况下以一分的优势赢得比赛，他只需要一直出剪刀。此时： 他赢了三轮（第二、第四和第六轮），Bob 出的是布； 他在第三轮平局，Bob 出的是剪刀； * 他输了两轮（第一和第五轮），Bob 出的是石头。

输入 2

KKPPNN

输出 2

1

在这里，如果 Johnny 不做任何改变，他只能以平局结束比赛。如果他做出一次改变，有很多种方式可以赢得比赛。其中一种可能的方式是前两轮出布，然后在剩下的比赛中改为出剪刀。此时： 出布时，他赢了第一和第二轮，Bob 出的是石头； 出剪刀时，他赢了第三和第四轮，Bob 出的是布； * 继续出剪刀，他在第五和第六轮平局，Bob 出的也是剪刀。