题目描述

为了备战 JOI 本选而练习编程的你，注意到今年的 JOI 预选只有数值计算题而没有字符串题。于是，你决定偷偷提高自己在字符串题上的实力，以甩开竞争对手。翻看过去的 JOI 题目后，你发现应该先熟悉由 J、O、I 这 $3$ 种字符构成的字符串。让我们来考虑这类字符串。你想出了“回答给定的字符串是否包含 JOI 作为子串”这个问题，并立刻解决了它。想要解决更高水平问题的你，创作了下面这道题目。

如果通过在字符串 $t$ 的开头和末尾添加若干个字符（也可以是 $0$ 个字符）能够得到字符串 $s$，则称 $t$ 是字符串 $s$ 的子串。例如，JJOOII 是 OJJOOIIOJOI 的子串。另一方面，JOI 不是 JOOI 的子串。

此外，对于大于或等于 $0$ 的整数 $k$，由 $k$ 个字符 J、$k$ 个字符 O、$k$ 个字符 I 按此顺序排列而成的字符串称为等级 $k$ 的 JOI 串。例如，JJOOII 是等级 $2$ 的 JOI 串。

我们想要在作为给定字符串的子串的 JOI 串中，找出等级最大的一个。

任务

给定由 J、O、I 这 $3$ 种字符构成的、长度为 $N$ 的字符串 $S$，请编写一个程序，求出使得等级 $k$ 的 JOI 串是 $S$ 的子串的 $k$ 的最大值。

限制

• $1 \le N \le 1000000 \ (= 10^6)$：$S$ 的长度。

输入格式

从标准输入读取以下数据。

• 第 $1$ 行写有一个由 J、O、I 这 $3$ 种字符构成的字符串 $S$。

输出格式

向标准输出输出 $1$ 行，表示使得等级 $k$ 的 JOI 串是 $S$ 的子串的 $k$ 的最大值的整数。

子任务

• 在占总分 $20\%$ 的评测数据中，满足 $N \le 100$。

样例 1

输入

OJJOOIIOJOI

输出

2

OJJOOIIOJOI 包含作为等级 $2$ 的 JOI 串的 JJOOII 作为子串，且不包含等级 $3$ 或以上的 JOI 串作为子串。

样例 2

输入

IJJIIJJJ

输出

0

等级 $0$ 的 JOI 串是长度为 $0$ 的字符串。

样例 3

输入

JOIJOIJOIJOIJOI

输出

1

样例 4

输入

OOJJJJJJOOOOIIIII

输出

4