题目描述

小明对字符串 IOI 怀有特殊的感情，他定义一种由大写英文字母 I 和 O 构成的字符串为“好串”，当且仅当它可以被划分为三个非空部分，依次为：

第一部分：连续若干个 I

第二部分：连续若干个 O

第三部分：连续若干个 I

如：

IIIOOIIII 是一个好串，IOI 也是一个好串；

OIOI，IIO 都不是好串。

现在，小明有一个长度为 $n$ 的字符串 $S$，且 $S$ 仅包含字符 I 和 O。

他可以进行任意次修改操作，每一次操作可将字符串中某一个位置的字符替换成另一个字符（即把 I 改为 O，或把 O 改为 I）。

例如：

当 $S = \tt{IIIOOOIOOII}$ 时，根据上述定义，$S$ 不是一个“好串”，但小明可以有多种方法通过修改操作把 $S$ 变为“好串”：

方法 1：把第 7 个字符 I 改为 O，经过 1 次操作得到 IIIOOOOOOII；

方法 2：分别把第 8 个和第 9 个字符 O 改为 I，经过 2 次操作得到 IIIOOOIIIII。

可以确定，至少经过 1 次修改操作才能把上面的字符串 $S$ 变为“好串”。

你的任务：

告诉你小明的字符串 $S$，请你帮小明计算，至少需要进行多少次修改操作，才能将字符串 $S$ 变为一个“好串”。如果 $S$ 已经是一个“好串”，输出 $0$。

输入格式

一行，仅由 I 和 O 两种字符组成的字符串 $S$。

输出格式

一行，包含一个整数，表示把字符串 $S$ 修改为“好串”需要的最少的修改次数。

IIIOOOIOOII

1

IOOIOOIOOOII

2

提示

【样例 3】

见选手目录下的 ioi/ex_ioi3.in 与 ioi/ex_ioi3.ans。

【样例 4】

见选手目录下的 ioi/ex_ioi4.in 与 ioi/ex_ioi4.ans。

【数据范围】

对于所有的数据，字符串的长度 $n$ 满足 $3 \le n \le 5 \times 10^3$，且字符串中仅包含大写英文字母 I 和 O。

::cute-table{tuack}

测试点	$n \le$	特殊性质
$1$	$1000$	字符全部为 I
$2$		字符全部为 O
$3\sim 13$	$200$	无
$14\sim 20$	$5 \times 10^3$