You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

海客谈瀛洲，烟涛微茫信难求；
越人语天姥，云霞明灭或可睹。
天姥连天向天横，势拔五岳掩赤城。
天台四万八千丈，对此欲倒东南倾。

我欲因之梦吴越，一夜飞度镜湖月。
湖月照我影，送我至剡溪。
谢公宿处今尚在，渌水荡漾清猿啼。
脚著谢公屐，身登青云梯。
半壁见海日，空中闻天鸡。
千岩万转路不定，迷花倚石忽已暝。
熊咆龙吟殷岩泉，栗深林兮惊层巅。
云青青兮欲雨，水澹澹兮生烟。
列缺霹雳，丘峦崩摧。
洞天石扉，訇然中开。
青冥浩荡不见底，日月照耀金银台。
霓为衣兮风为马，云之君兮纷纷而来下。
虎鼓瑟兮鸾回车，仙之人兮列如麻。

忽魂悸以魄动，恍惊起而长嗟。
惟觉时之枕席，失向来之烟霞。
世间行乐亦如此，古来万事东流水。
别君去兮何时还？且放白鹿青崖间，须行即骑访名山。
安能摧眉折腰事权贵，使我不得开心颜！

题目描述

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 解释

字符形成的环如下图所示：

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

样例 2 解释

字符形成的环如下图所示，这里需要替换 7 个字符。

从画圈的字符开始读取这个字符环一周，得到 JJJJOOOOIIIIJOIJ 字符串，这是一个级别为 2 的 JOI 列，并且是替换次数最少的情况，因此输出 7。

数据范围

所有输入数据均满足以下条件：

• $1 \leq K \leq 10$。

子任务

子任务 1 [30 分]

• $K \leq 5$。

子任务 2 [70 分]

无额外限制。