K 理事长决定为日本信息学奥林匹克竞赛的选手们设计一款应援周边商品的 Logo。有一天，K 理事长想到可以将 ‘J’、‘O’、‘I’ 三个字符排列成圆形作为 Logo。这其中寄托了希望大家能够享受（enjoy）JOI 的心愿。

对于 0 以上的整数 $k$，我们定义“$k$ 级 JOI 序列”如下：

• 0 级 JOI 序列是 ‘J’、‘O’、‘I’ 中的任意一个字符。
• $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 \le K \le 10$

子任务

1. （30 分）满足 $K \le 5$。
2. （70 分）没有额外限制。

样例

样例输入 1

1
IJOI

样例输出 1

0

纸上的字符圆状排列如下：

从 ‘J’ 开始顺时针读完一圈为 “JOII”，这是一个 1 级 JOI 序列。K 理事长不需要修改任何字符，因此输出 0。

样例输入 2

2
JJOIJJOJOIOJOOOI

样例输出 2

7

纸上的字符圆状排列如下（左图）。修改其中 7 处后变为右图所示。

从带有 ○ 的字符开始顺时针读完一圈为 “JJJJOOOOIIIIJOIJ”，这是一个 2 级 JOI 序列。这是修改字符数的最小值，因此输出 7。