P14406 [JOISC 2015] 愉快的标志设计 / En-JOI-able Logo Design

K 理事长计划为日本信息奥林匹克（JOI）选手设计一款支持用的周边商品的标志。某天，K 理事长想到，可以将字符 ‘J’、‘O’、‘I’ 按顺序排列组成一个环形标志。这个设计蕴含着希望 JOI 的参与者能够享受（enjoy）竞赛的寓意。 以下是对整数 $k \geq 0$ 定义的“级别 $k$ 的 JOI 序列”： - 级别 0 的 JOI 序列是由 ‘J’、‘O’、‘I’ 中任意一个字符组成的长度为 1 的字符串。 - 级别 $k+1$ 的 JOI 序列是一个长度为 $4^{k+1}$ 的字符串，其结构如下：前 $4^k$ 个字符全部为 ‘J’，接下来的 $4^k$ 个字符全部为 ‘O’，再接下来的 $4^k$ 个字符全部为 ‘I’，最后的 $4^k$ 个字符构成一个级别 $k$ 的 JOI 序列。 现在，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 解释 字符形成的环如下图所示： :::align{center}  ::: 以 J 为起点顺时针读取一周，形成的字符串为 JOII，这是一个级别为 1 的 JOI 列。K 理事长没必要替换字符，所以输出 0。 ### 样例 2 解释 字符形成的环如下图所示，这里需要替换 7 个字符。 :::align{center}  ::: 从画圈的字符开始读取这个字符环一周，得到 JJJJOOOOIIIIJOIJ 字符串，这是一个级别为 2 的 JOI 列，并且是替换次数最少的情况，因此输出 7。 ### 数据范围 所有输入数据均满足以下条件： - $1 \leq K \leq 10$。 ### 子任务 #### 子任务 1 [30 分] - $K \leq 5$。 #### 子任务 2 [70 分] 无额外限制。