Với số nguyên \(k\ge0\), một dãy JOI cấp \(k\) được định nghĩa như sau:

• Cấp 0 là một ký tự J, O hoặc I.
• Dãy cấp \(k+1\) dài \(4^{k+1}\): \(4^k\) ký tự đầu đều là J, \(4^k\) ký tự tiếp đều là O, \(4^k\) ký tự tiếp đều là I, và \(4^k\) ký tự cuối tạo thành một dãy JOI cấp \(k\).

Có \(4^K\) ký tự J, O, I viết trên một vòng tròn. Được phép thay đổi một số ký tự. Hãy tìm số thay đổi ít nhất để khi chọn một điểm bắt đầu thích hợp và đọc một vòng theo chiều kim đồng hồ, ta được một dãy JOI cấp \(K\).

Dữ liệu vào

Dòng đầu chứa \(K\). Dòng sau là xâu dài \(4^K\), thu được khi đọc vòng tròn từ một điểm cố định theo chiều kim đồng hồ.

Dữ liệu ra

In số ký tự ít nhất phải thay đổi.

Ràng buộc

Phân nhóm

• Nhóm 1 (30 điểm): \(K\le5\).
• Nhóm 2 (70 điểm): không có ràng buộc bổ sung.

Ví dụ

1
IJOI

0

2
JJOIJJOJOIOJOOOI

7