学校食堂的包子摊前有n个小学生,男生女生,排着队。面包还没有准备好,生产线正在发生一些变化。
每一秒,所有站在女孩面前的男孩都会同时与女孩交换位置(这样女孩就可以更接近队伍的开头)。换句话说,如果在某个时刻第i个位置是男孩,第(i+1)个位置是女孩,那么在一秒钟内,第i个位置将是女孩,第(i+1)个位置将是男孩。
我们以四个人的队伍为例:一个男孩,一个男孩,一个女孩,一个女孩(从队伍的开始到结束)。下一秒,这条线将如下所示:一个男孩,一个女孩,一个男孩,一个女孩。下一秒就会是女孩,男孩,女孩,男孩。下一秒就会是女孩,女孩,男孩,男孩。线路不会再变了。
你的任务是:根据孩子们在队列中的排列情况,确定将所有女孩移到男孩前面所需的时间(在上面的示例中需要 3 秒)。烤面包需要很长时间,所以直到队伍停止换线之前都没有人离开队伍。
输入
第一行包含不带空格的字母序列 s1s2...sn (1 ≤ n ≤ 106),由大写英文字母 M 和 F 组成。如果字母 si 等于 M,则表示最初该行第 i 个位置上有一个男孩。如果字母 si 等于 F,则最初该行的第 i 个位置上有一个女孩。
输出
打印一个整数 - 将队列中的所有女孩移动到男孩前面所需的秒数。如果该行只有男孩或只有女孩,则打印 0。
示例
输入 #1
MFM
输出 #1
1
输入 #2
MMFF
输出 #2
3
输入 #3
FFMMM
输出 #3
0
注意
在第一个测试用例中,更改顺序如下:MFM → FMM。
第二个测试样本对应于声明中的样本。变化顺序为:MMFF→MFMF→FMFM→FFMM。