Problem Statement

Practicing programming for the JOI Final Round, you noticed that this year's JOI Preliminary Round had only numerical problems and no string problems. So you decided to secretly get strong at string problems to get ahead of your rivals. Looking at past JOI problems, you found that you should get used to strings consisting of the $3$ types of characters J, O, and I. Let us consider such strings. You came up with the problem "Answer whether a given string has JOI as a substring", which you solved immediately. Wanting to solve a higher-level problem, you created the following problem.

String $t$ is a substring of string $s$ if $s$ can be obtained by appending some number of characters ($0$ characters is also allowed) to the beginning and end of $t$. For example, JJOOII is a substring of OJJOOIIOJOI. On the other hand, JOI is not a substring of JOOI.

Also, for an integer $k$ greater than or equal to $0$, a JOI-string of level $k$ is a string formed by arranging $k$ characters J, $k$ characters O, and $k$ characters I in this order. For example, JJOOII is a JOI-string of level $2$.

We want to find the one with the maximum level among the JOI-strings that are substrings of the given string.

Task

Given a string $S$ of length $N$ consisting of the $3$ types of characters J, O, and I, write a program to find the maximum value of $k$ such that the JOI-string of level $k$ is a substring of $S$.

Limits

• $1 \le N \le 1000000 \ (= 10^6)$: The length of $S$.

Input

Read the following data from standard input.

• On the $1$-st line, a string $S$ consisting of the $3$ types of characters J, O, and I is written.

Output

Output to standard output on $1$ line an integer representing the maximum value of $k$ such that the JOI-string of level $k$ is a substring of $S$.

Subtasks

• For $20\%$ of the points in the grading data, $N \le 100$ is satisfied.

Sample 1

Input

OJJOOIIOJOI

Output

2

OJJOOIIOJOI contains JJOOII, which is the JOI-string of level $2$, as a substring, and does not contain any JOI-string of level $3$ or higher as a substring.

Sample 2

Input

IJJIIJJJ

Output

0

The JOI-string of level $0$ is a string of length $0$.

Sample 3

Input

JOIJOIJOIJOIJOI

Output

1

Sample 4

Input

OOJJJJJJOOOOIIIII

Output

4