Énoncé du problème

Alors que vous vous entraîniez à la programmation pour la finale de la JOI, vous avez remarqué que le tour préliminaire de la JOI de cette année ne comportait que des problèmes numériques et aucun problème de chaînes de caractères. Vous avez donc décidé de devenir secrètement très fort sur les problèmes de chaînes de caractères pour prendre de l'avance sur vos rivaux. En regardant les anciens problèmes de la JOI, vous avez constaté qu'il fallait vous habituer aux chaînes composées des $3$ types de caractères J, O et I. Considérons de telles chaînes. Vous avez imaginé le problème « Répondre si une chaîne donnée contient JOI comme sous-chaîne », que vous avez résolu immédiatement. Voulant résoudre un problème d'un niveau plus élevé, vous avez créé le problème suivant.

Une chaîne $t$ est une sous-chaîne d'une chaîne $s$ si $s$ peut être obtenue en ajoutant un certain nombre de caractères ($0$ caractère est également permis) au début et à la fin de $t$. Par exemple, JJOOII est une sous-chaîne de OJJOOIIOJOI. En revanche, JOI n'est pas une sous-chaîne de JOOI.

De plus, pour un entier $k$ supérieur ou égal à $0$, une chaîne-JOI de niveau $k$ est une chaîne formée en disposant $k$ caractères J, $k$ caractères O et $k$ caractères I dans cet ordre. Par exemple, JJOOII est une chaîne-JOI de niveau $2$.

Nous voulons trouver celle ayant le niveau maximal parmi les chaînes-JOI qui sont des sous-chaînes de la chaîne donnée.

Tâche

Étant donné une chaîne $S$ de longueur $N$ composée des $3$ types de caractères J, O et I, écrivez un programme permettant de trouver la valeur maximale de $k$ telle que la chaîne-JOI de niveau $k$ soit une sous-chaîne de $S$.

Limites

• $1 \le N \le 1000000 \ (= 10^6)$ : la longueur de $S$.

Entrée

Lisez les données suivantes depuis l'entrée standard.

• Sur la $1$-re ligne est écrite une chaîne $S$ composée des $3$ types de caractères J, O et I.

Sortie

Affichez sur la sortie standard, sur $1$ ligne, un entier représentant la valeur maximale de $k$ telle que la chaîne-JOI de niveau $k$ soit une sous-chaîne de $S$.

Sous-tâches

• Pour $20\%$ des points des données d'évaluation, $N \le 100$ est vérifié.

Exemple 1

Entrée

OJJOOIIOJOI

Sortie

2

OJJOOIIOJOI contient JJOOII, qui est la chaîne-JOI de niveau $2$, comme sous-chaîne, et ne contient aucune chaîne-JOI de niveau $3$ ou plus comme sous-chaîne.

Exemple 2

Entrée

IJJIIJJJ

Sortie

0

La chaîne-JOI de niveau $0$ est une chaîne de longueur $0$.

Exemple 3

Entrée

JOIJOIJOIJOIJOI

Sortie

1

Exemple 4

Entrée

OOJJJJJJOOOOIIIII

Sortie

4