題目描述

為了備戰 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