Условие задачи

Тренируясь в программировании перед финальным этапом JOI, вы заметили, что в отборочном этапе JOI этого года были только числовые задачи и ни одной задачи на строки. Поэтому вы решили тайно прокачаться в строковых задачах, чтобы опередить своих соперников. Просматривая прошлые задачи JOI, вы поняли, что стоит привыкнуть к строкам, состоящим из $3$ видов символов: J, O и I. Давайте рассмотрим такие строки. Вы придумали задачу «Ответьте, содержит ли данная строка JOI в качестве подстроки», которую тут же решили. Желая решить задачу более высокого уровня, вы составили следующую задачу.

Строка $t$ называется подстрокой строки $s$, если $s$ можно получить, приписав некоторое количество символов ($0$ символов тоже допускается) в начало и в конец строки $t$. Например, JJOOII является подстрокой OJJOOIIOJOI. С другой стороны, JOI не является подстрокой JOOI.

Кроме того, для целого числа $k$, большего или равного $0$, JOI-строкой уровня $k$ называется строка, образованная выписыванием подряд $k$ символов J, $k$ символов O и $k$ символов I в этом порядке. Например, JJOOII — это JOI-строка уровня $2$.

Мы хотим найти строку с максимальным уровнем среди всех JOI-строк, являющихся подстроками данной строки.

Задача

Дана строка $S$ длины $N$, состоящая из $3$ видов символов J, O и I. Напишите программу, которая находит максимальное значение $k$, при котором JOI-строка уровня $k$ является подстрокой $S$.

Ограничения

• $1 \le N \le 1000000 \ (= 10^6)$: длина строки $S$.

Входные данные

Считайте следующие данные из стандартного потока ввода.

• В $1$-й строке записана строка $S$, состоящая из $3$ видов символов J, O и I.

Выходные данные

Выведите в стандартный поток вывода в $1$ строке целое число — максимальное значение $k$, при котором JOI-строка уровня $k$ является подстрокой $S$.

Подзадачи

• Для $20\%$ баллов в тестовых данных выполняется $N \le 100$.

Пример 1

Ввод

OJJOOIIOJOI

Вывод

2

OJJOOIIOJOI содержит JJOOII, то есть JOI-строку уровня $2$, в качестве подстроки, и не содержит ни одной JOI-строки уровня $3$ или выше в качестве подстроки.

Пример 2

Ввод

IJJIIJJJ

Вывод

0

JOI-строка уровня $0$ — это строка длины $0$.

Пример 3

Ввод

JOIJOIJOIJOIJOI

Вывод

1

Пример 4

Ввод

OOJJJJJJOOOOIIIII

Вывод

4