問題文

E869120国ではIOI国に続き, 新たに鉄道を敷設した。

E869120国の鉄道を走る列車はいくつかの車両が連結されたものであり, 車両には I, O の 2 種類がある。

しかし, 次のような規則でつながなければならない。

• 車両はそれぞれ異なる種類の車両としか連結できない。
• 列車に運転席を設ける関係上，列車の両端の車両は種類 I でなければならない。

列車は車両の種類を表す文字を順につなげた文字列で表され, 列車の長さはその文字列の長さであるとする。

例えば, IOIOI , IOIOIOIOIOIOIOIOI などが条件を満たす。

今, 車庫には文字列 S で表されるような車両が連結された状態がある。

編成する車両は, S の部分列でなければならない。

そのとき, 最大で何両の列車が編成できるだろうか。