愉快的标志设计

题号：NC53267
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

译自 JOISC 2015 Day1 T2「愉快なロゴデザイン / En-JOI-able Logo Design」

K理事长想要设计一个应援日本信息学奥林匹克选手的标志。某天，K理事长想到了用环状排列的J，O，I作为标志，希望选手享受JOI的比赛。
（注：日语中「円状JOI」的发音与英文单词enjoy相似，故有此意。）
级别为 $k \ (k \ge 0)$ 的JOI列定义如下：

级别为0的JOI列是由J，O，I字母之一形成的字符串；
级别为k+1的JOI列是这样构造的：最初 $4^k$ 个字母是J，然后 $4^k$ 个字母是O，然后 $4^k$ 个字母是I，最后 $4^k$ 个字符是级别为k的JOI列，级别为k+1的JOI列长度为 $4^{k+1}$ 。

现在，K理事长写了一个长为 $4^K$ 的环形字符串，字符环只包含J，O，I三种字符。K理事长会修改一些字符，使得从这个环上某一位开始，顺时针读取这个环形字符串一周，能得到一个级别为K的JOI列。此时，要求最小化修改次数。
现在给出K与长度为 $4^K$ 的字符串，现要替换一些字符，使其从环上某位置开始顺时针读取这个字符环，能得到一个K级JOI列，要求最小化替换字符数。

输入描述:

第一行一个整数$K$，表示环上有$4^K$个字符；
第二行一个只包含J，O，I的长为$4^K$的字符串，表示从某一个位置顺时针读取字符环一周，会得到这个字符串。

输出描述:

输出一行，表示K理事长替换字符的最少次数。

示例1

输入

复制

1
IJOI

输出

复制

说明

字符形成的环如下图所示：
以J为起点顺时针读取一周，形成的字符串为JOII，这是一个级别为1的JOI列。K理事长没必要替换字符，所以输出0。

示例2

输入

复制

2
JJOIJJOJOIOJOOOI

输出

复制

说明

字符形成的环如下图所示：
这里需要替换7个字符。
从画圈的字符开始读取这个字符环一周，得到JJJJOOOOIIIIJOIJ字符串，这是一个级别为2的JOI列，并且是替换次数最少的情况，因此输出7。

备注:

对于全部数据，。

CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/2995