001 - 愉快なロゴデザイン (En-JOI-able Logo Design)

問題

　K 理事長は，日本情報オリンピックの選手を応援するグッズのロゴを考えることとなった．ある日 K 理事長は，円状に ‘J’， ‘O’， ‘I’ の文字を並べたものをロゴとすることを思いついた．これには JOI を楽しんで (enjoy) もらいたいとする思いが込められている．
　以下のように，0 以上の整数 k に対してレベル k の JOI 列というものを定める．

• レベル 0 の JOI 列とは，‘J’， ‘O’， ‘I’ のいずれかの 1 文字からなる文字列である．
• レベル k + 1 の JOI 列とは，最初の 4^k 文字がすべて ‘J’，次の 4^k 文字がすべて ‘O’，次の 4^k 文字がすべて ‘I’ であり，最後の 4^k 文字がレベル k の JOI 列であるような，長さが 4^k+1 の文字列である．

　今，K 理事長は，4^K 個の文字が円状に書かれた紙を持っている．紙に書かれた文字は，‘J’， ‘O’， ‘I’ のいずれかである．K 理事長は，いくつかの文字を書き換えて，紙に書かれた文字が，ある文字を起点に時計回りに一周読むとレベル K の JOI 列になるようにする．このとき，書き換える文字数をなるべく少なくしたい．

課題

　紙に円状に書き並べられた長さ 4^K の文字列が与えられたとき，これをある文字を起点に時計回りに一周読むとレベル K の JOI 列になるようにするために必要な，書き換える文字数の最小値を求めるプログラムを作成せよ．

入力

　標準入力から以下のデータを読み込め．

• 1 行目には，整数 K が書かれている．これは，4^K 個の文字が紙に円状に書かれていることを表す．
• 2 行目には，‘J’，‘O’，‘I’ からなる長さ 4^K の文字列が書かれている．これは，紙に書かれた文字を，ある文字を起点に時計回りに一周読むと，この文字列になることを表す．

出力

　標準出力に，K 理事長が書き換える文字数の最小値を 1 行で出力せよ．

制限

　すべての入力データは以下の条件を満たす．

• 1 ≤ K ≤ 10．

小課題

小課題 1 [30 点]

• K ≤ 5 を満たす．

小課題 2 [70 点]

　追加の制限はない．

入出力例

入力例　1

1
IJOI

出力例 1

0

　紙には下図のように文字が円状に書かれている．

　‘J’ を起点に時計回りに一周読むと “JOII” となり，これはレベル 1 の JOI 列である．K 理事長は文字を書き換える必要がないので， 0 を出力する．

入力例　2

2
JJOIJJOJOIOJOOOI

出力例 2

7

　紙には下図の左のように文字が円状に書かれている．このうち 7 箇所を書き換えると右のようになる．

→

　○の付いた文字を起点に時計回りに一周読むと，“JJJJOOOOIIIIJOIJ” となり，これはレベル 2 の JOI 列である．これが書き換える文字数の最小値なので，7 を出力する．