Trong khi luyện lập trình để chuẩn bị cho vòng chung kết JOI, bạn nhận ra rằng các bài ở vòng sơ khảo năm nay đều xử lý số và không có bài nào xử lý xâu. Bạn quyết định âm thầm luyện các bài về xâu để vượt lên các đối thủ.

Xem lại các đề JOI trước đây, bạn thấy cần làm quen với những xâu chỉ gồm ba ký tự J, O, I. Bài toán kiểm tra một xâu có chứa xâu con JOI quá dễ, nên bạn nghĩ ra bài toán khó hơn dưới đây.

Xâu \(t\) là xâu con của xâu \(s\) nếu có thể thêm một số ký tự (có thể là \(0\)) vào đầu và cuối \(t\) để thu được \(s\). Nói cách khác, các ký tự của \(t\) phải xuất hiện liên tiếp trong \(s\). Chẳng hạn, JJOOII là xâu con của OJJOOIIOJOI, nhưng JOI không phải là xâu con của JOOI.

Với số nguyên \(k\ge0\), xâu JOI cấp \(k\) là xâu gồm \(k\) ký tự J, tiếp theo là \(k\) ký tự O, rồi \(k\) ký tự I. Ví dụ, JJOOII là xâu JOI cấp \(2\). Xâu JOI cấp \(0\) là xâu rỗng.

Yêu cầu

Cho xâu \(S\) có độ dài \(N\), chỉ gồm các ký tự J, O, I. Hãy tìm số nguyên \(k\) lớn nhất sao cho xâu JOI cấp \(k\) là xâu con của \(S\).

Dữ liệu vào

Đọc từ đầu vào chuẩn một dòng chứa xâu \(S\). Độ dài \(N\) không được cho riêng trong đầu vào.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số nguyên \(k\) lớn nhất thỏa mãn yêu cầu.

Ràng buộc

• \(1\le N\le1\,000\,000\).
• \(S\) chỉ gồm các ký tự J, O, I.

Phân nhóm

• \(20\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le100\).

Ví dụ

OJJOOIIOJOI

2

IJJIIJJJ

0

JOIJOIJOIJOIJOI

1

OOJJJJJJJOOOOIIIII

4