問題文

JOI 本選に向けてプログラミングの練習をしていたあなたは，今年の JOI 予選の問題には数値の問題ばかりで文字列の問題がなかったことに気がついた．そこであなたは，こっそり文字列の問題に強くなってライバルたちに差をつけることにした．過去の JOI の問題を見ていると，J，O，I の $3$ 種類の文字からなる文字列に慣れる必要がありそうなことがわかった．そこで，そのような文字列について考えてみることにした．あなたは「与えられた文字列が部分文字列として JOI を持つか答えよ」という問題を思いついたが，これはすぐに解けてしまった．もっとレベルの高い問題を解きたいと思ったあなたは，以下のような問題を作った．

文字列 $t$ が文字列 $s$ の部分文字列であるとは，$t$ の先頭および末尾に何文字か（$0$ 文字でもよい）付け足すと $s$ になることである．たとえば，JJOOII は OJJOOIIOJOI の部分文字列である．一方，JOI は JOOI の部分文字列ではない．

また，$0$ 以上の整数 $k$ に対し，レベル $k$ の JOI 列とは，$k$ 個の文字 J，$k$ 個の文字 O，$k$ 個の文字 I をこの順に並べた文字列のことである．たとえば，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$ が書かれている．

出力

標準出力に，レベル $k$ の JOI 列が $S$ の部分文字列となるような最大の $k$ の値を表す整数を $1$ 行で出力せよ．

採点基準

• 採点用データのうち，配点の $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