Director K has decided to design a logo for goods to support the participants of the Japanese Olympiad in Informatics. One day, Director K came up with the idea of using a circular arrangement of the characters 'J', 'O', and 'I' as the logo. This embodies the wish for people to enjoy JOI.

We define a level $k$ JOI sequence for an integer $k \ge 0$ as follows: A level 0 JOI sequence is a string consisting of a single character, either 'J', 'O', or 'I'. A level $k+1$ JOI sequence is a string of length $4^{k+1}$ such that the first $4^k$ characters are all 'J', the next $4^k$ characters are all 'O', the next $4^k$ characters are all 'I', and the last $4^k$ characters form a level $k$ JOI sequence.

Director K has a piece of paper with $4^K$ characters written in a circle. The characters on the paper are 'J', 'O', or 'I'. Director K wants to rewrite some of the characters so that the sequence of characters on the paper, when read clockwise starting from some character, becomes a level $K$ JOI sequence. He wants to minimize the number of characters rewritten.

Task

Given a string of length $4^K$ written in a circle on paper, write a program to find the minimum number of characters that need to be rewritten so that the sequence, when read clockwise starting from some character, becomes a level $K$ JOI sequence.

Input

Read the following data from standard input: The first line contains an integer $K$. This represents that $4^K$ characters are written in a circle on the paper. The second line contains a string of length $4^K$ consisting of 'J', 'O', and 'I'. This represents the characters on the paper when read clockwise starting from a certain character.

Output

Output the minimum number of characters Director K needs to rewrite in a single line to standard output.

Constraints

All input data satisfies the following condition: * $1 \le K \le 10$.

Subtasks

Subtask 1 [30 points]

• $K \le 5$ is satisfied.

Subtask 2 [70 points]

• There are no additional constraints.

Examples

Input 1

1
IJOI

Output 1

0

The characters are written in a circle on the paper as shown in the figure below.

Reading clockwise starting from 'J' gives "JOII", which is a level 1 JOI sequence. Since Director K does not need to rewrite any characters, he outputs 0.

Input 2

2
JJOIJJOJOIOJOOOI

Output 2

7

The characters are written in a circle on the paper as shown on the left in the figure below. Rewriting 7 of these characters results in the arrangement on the right.

Reading clockwise starting from the character marked with a circle gives "JJJJOOOOIIIIJOIJ", which is a level 2 JOI sequence. Since this is the minimum number of characters to rewrite, he outputs 7.