Descrizione del problema

Mentre ti allenavi nella programmazione per la fase finale della JOI, hai notato che la fase preliminare della JOI di quest'anno conteneva solo problemi numerici e nessun problema sulle stringhe. Così hai deciso di diventare segretamente molto forte sui problemi sulle stringhe per superare i tuoi rivali. Guardando i problemi passati della JOI, hai scoperto che dovresti abituarti alle stringhe composte dai $3$ tipi di caratteri J, O e I. Consideriamo tali stringhe. Ti è venuto in mente il problema «Rispondi se una stringa data ha JOI come sottostringa», che hai risolto immediatamente. Volendo risolvere un problema di livello più alto, hai creato il problema seguente.

Una stringa $t$ è una sottostringa di una stringa $s$ se $s$ può essere ottenuta aggiungendo un certo numero di caratteri ($0$ caratteri è pure consentito) all'inizio e alla fine di $t$. Ad esempio, JJOOII è una sottostringa di OJJOOIIOJOI. D'altra parte, JOI non è una sottostringa di JOOI.

Inoltre, per un intero $k$ maggiore o uguale a $0$, una stringa-JOI di livello $k$ è una stringa formata disponendo $k$ caratteri J, $k$ caratteri O e $k$ caratteri I in quest'ordine. Ad esempio, JJOOII è una stringa-JOI di livello $2$.

Vogliamo trovare quella con il livello massimo tra le stringhe-JOI che sono sottostringhe della stringa data.

Compito

Data una stringa $S$ di lunghezza $N$ composta dai $3$ tipi di caratteri J, O e I, scrivi un programma per trovare il valore massimo di $k$ tale che la stringa-JOI di livello $k$ sia una sottostringa di $S$.

Limiti

• $1 \le N \le 1000000 \ (= 10^6)$: La lunghezza di $S$.

Input

Leggi i seguenti dati dallo standard input.

• Sulla $1$-a riga è scritta una stringa $S$ composta dai $3$ tipi di caratteri J, O e I.

Output

Stampa sullo standard output su $1$ riga un intero che rappresenta il valore massimo di $k$ tale che la stringa-JOI di livello $k$ sia una sottostringa di $S$.

Sottoproblemi

• Per il $20\%$ dei punti nei dati di valutazione, vale $N \le 100$.

Esempio 1

Input

OJJOOIIOJOI

Output

2

OJJOOIIOJOI contiene JJOOII, che è la stringa-JOI di livello $2$, come sottostringa, e non contiene alcuna stringa-JOI di livello $3$ o superiore come sottostringa.

Esempio 2

Input

IJJIIJJJ

Output

0

La stringa-JOI di livello $0$ è una stringa di lunghezza $0$.

Esempio 3

Input

JOIJOIJOIJOIJOI

Output

1

Esempio 4

Input

OOJJJJJJOOOOIIIII

Output

4