시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 6 5 5 83.333%

문제

K 理事長は,日本情報オリンピックの選手を応援するグッズのロゴを考えることとなった.ある日 K 理 事長は,円状に ‘J’, ‘O’, ‘I’ の文字を並べたものをロゴとすることを思いついた.これには JOI を楽 しんで (enjoy) もらいたいとする思いが込められている.

以下のように,0 以上の整数 k に対してレベル k の JOI 列というものを定める.

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

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

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

입력

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

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

출력

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

제한

  • 1 ≦ K ≦ 10.

예제 입력 1

1
IJOI

예제 출력 1

0

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

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

예제 입력 2

2
JJOIJJOJOIOJOOOI

예제 출력 2

7

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

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