Problem Description

You were practicing programming for the final round of the JOI (Japanese Olympiad in Informatics) when you noticed that all the problems in this year's qualifying round dealt with numbers and there were no problems involving strings. Determined to gain an edge over your rivals, you decided to secretly strengthen your skills in string problems.

While looking through past JOI problems, you realized that it would be beneficial to get familiar with strings consisting of the three characters J, O, and I. You came up with a problem to determine if a given string contains the substring JOI, but you quickly solved it. Eager for a more challenging problem, you devised the following:

A string \( t \) is a substring of string \( s \) if \( t \) can be transformed into \( s \) by adding some characters (possibly zero) 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.

For a non-negative integer \( k \), a level \( k \) JOI string is defined as a string consisting of \( k \) characters J, followed by \( k \) characters O, followed by \( k \) characters I. For example, JJOOII is a level 2 JOI string.

You want to find the maximum level of a JOI string that is a substring of the given string.

Input Format

Read the following data from standard input:

• The first line contains a string \( S \) consisting of the three characters J, O, and I.

Output Format

Output a single integer on one line, representing the maximum value of \( k \) such that a level \( k \) JOI string is a substring of \( S \).

Sample Input and Output

Sample Input #1

OJJOOIIOJOI

Sample Output #1

2

Sample Input #2

IJJIIJJJ

Sample Output #2

0

Sample Input #3

JOIJOIJOIJOIJOI

Sample Output #3

1

Sample Input #4

OOJJJJJJJOOOOIIIII

Sample Output #4

4

Notes/Hints

Task

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

Constraints

\( 1 \leq N \leq 1,000,000 \) ( \( = 10^6 \) ) - Length of \( S \)

Grading Criteria

For 20% of the test cases, \( N \leq 100 \).

Sample Explanation 1

OJJOOIIOJOI contains the level 2 JOI string JJOOII as a substring, but does not contain any level 3 or higher JOI strings as substrings.

Sample Explanation 2

A level 0 JOI string is an empty string.

Sample Explanation 3

-

见题面 Input 部分

见题面 Output 部分