JOI (日本情報オリンピック) の本選に向けてプログラミングの練習をしていたあなたは，今年度の JOI の予選の問題には数値を扱う問題ばかりが出題され，文字列を扱う問題がなかったことに気がついた．そこであなたは，こっそり文字列の問題に強くなってライバルたちに差をつけることにした．

JOIの過去問を眺めていると，J，O，I の 3 種類の文字からなる文字列に慣れておく必要がありそうなことがわかった．そこで，そのような文字列について考えよう．あなたは「与えられた文字列が JOI という部分文字列をもつかどうかを答えよ」という問題を思いついたものの，これはすぐに解けてしまった．もっとレベルの高い問題を解きたいあなたは，以下のような問題を作った．

文字列 t が文字列 s の部分文字列であるとは，t の先頭および末尾に何文字か (0 文字でもよい) を付け足すと s になることである．たとえば，JJOOII は OJJOOIIOJOI の部分文字列である．一方，JOI は JOOI の部分文字列ではない．

また，0 以上の整数 k に対し，レベル k の JOI 列とは，k 個の文字 J，k 個の文字 O，k 個の文字 I をこの順に並べた文字列のことであるとする．たとえば，JJOOII はレベル 2 の JOI 列である．

与えられた文字列の部分文字列である JOI 列のうち，レベルが最大のものを求めたい．

課題

J，O，I の 3 種類の文字からなる長さ N の文字列 S が与えられたとき，レベル k の JOI 列が S の部分文字列であるような最大の k の値を求めるプログラムを作成せよ．

制限

採点基準

採点用データのうち，配点の 20 %分については，N \leqq 100 を満たす．

入力例 1

OJJOOIIOJOI

出力例 1

2

OJJOOIIOJOI はレベル 2 の JOI 列である JJOOII を部分文字列として含んでおり， レベル 3 以上の JOI 列は部分文字列として含まない．

入力例 2

IJJIIJJJ

出力例 2

0

レベル 0 の JOI 列は長さ 0 の文字列である．

入力例 3

JOIJOIJOIJOIJOI

出力例 3

1

入力例 4

OOJJJJJJJOOOOIIIII

出力例 4

4

1 から 1000 までのどれかの整数が書かれたカードがたくさんある．アンナとブルーノはそれらのカードを用いて，次のようなゲームをする．

アンナは A 枚，ブルーノは B 枚のカードからなる山を持つ．アンナは A 枚のカードの中から任意の何枚か (0 枚でもよい) を捨てて新しい山を作る．ブルーノは B 枚のカードからなる山の一番上から何枚か (0 枚でもよい) と，一番下から何枚か (0 枚でもよい) を捨てて新しい山を作る．ただし，捨てる際に残ったカードの並び替えは行わない．このように作った 2 つの山が一致していたら，一方の山に含まれるカードの枚数が 2 人の得点になる．ただし，2 つの山が一致するとは，山に含まれるカードの枚数 n が同じで，かつ上から i 番目 (1 \leqq i \leqq n) に書かれたカードの整数が全て同じであることである．

例えば，アンナが 5 枚のカードの山を持ち，書かれている整数は上から順に 1, 2, 3, 4, 5 であり，ブルーノが 4 枚のカードの山を持ち，書かれている整数が上から順に 3, 1, 4, 1 であったとする．このとき，アンナが 2, 3, 5 のカードを捨て，ブルーノが一番上の 3 と一番下の 1 のカードを捨てると 2 人の山が一致する．このとき，残った山の一方に含まれるカードの枚数は 2 枚なので， 2 人は得点 2 を得る．

2 人の得点の最大値を求めたい．

アンナ

ブルーノ

課題

アンナとブルーノが持っているカードの山の情報が与えられたときに，2 人の得点の最大値を求めるプログラムを作成せよ．

制限

採点基準

採点用データのうち，配点の 10 %分については，A \leqq 10, B \leqq 10 を満たす．

採点用データのうち，配点の 50 %分については，A \leqq 100, B \leqq 100 を満たす．

入力例 1

5 4
1 2 3 4 5
3 1 4 1

出力例 1

2

この入出力例は問題文中の例に対応している．

入力例 2

6 5
4 1 5 2 3 4
4 5 4 2 3

出力例 2

3

この入出力例では，2 人が得点 3 を得る方法が 2 通り存在する．アンナが 1, 2, 3 のカードを捨てブルーノが 2, 3 のカードを捨てたとき，2 人の山は上から順に 4, 5, 4 となり，2 人の得点は 3 点となる．また，アンナが 1, 5, 4 のカードを捨てブルーノが一番上の 4 と 5 のカードを捨てたとき，2 人の山は上から順に 4, 2, 3 となり，2 人の得点は 3 点となる．