题目描述

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
IJOI

0

2
JJOIJJOJOIOJOOOI

7

提示

样例 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 分]

无额外限制。