JJOOII

We work with strings made up of only the three characters J, O, and I.

A string $t$ is a substring of a string $s$ if $s$ can be formed by adding zero or more characters to both the front and the back of $t$; that is, $t$ must appear contiguously inside $s$. For example, JJOOII is a substring of OJJOOIIOJOI, whereas JOI is not a substring of JOOI.

For a non-negative integer $k$, a level-$k$ JOI sequence is the string consisting of $k$ copies of J, then $k$ copies of O, then $k$ copies of I, in that order. For example, JJOOII is a level-$2$ JOI sequence.

You are given a string $S$ of length $N$ over the characters J, O, and I. Find the largest $k$ such that a level-$k$ JOI sequence is a substring of $S$.

The first line contains the string $S$, made up of the characters J, O, and I.

Print, on a single line, the largest $k$ such that a level-$k$ JOI sequence is a substring of $S$. (If no level-$1$-or-higher JOI sequence is a substring, print 0.)

• $1 \le N \le 1,000,000$, where $N$ is the length of $S$.