There are $N$ shops along a main street in the JOI shopping district, numbered $1, 2, \dots, N$ from the entrance to the exit. The JOI shopping district is one-way, and one can only move from the entrance toward the exit.

To revitalize the town, a stamp rally will be held in the JOI shopping district. In this stamp rally, each shop provides one of the stamps 'J', 'O', or 'I', and people who shop at a store get a stamp on their stamp card. Participants in the stamp rally enter exactly three shops. At the entrance of the shopping district, a stamp card with three slots is distributed, and participants get stamps from the first, second, and third shops they visit. A campaign has been implemented where, if the stamps collected on the stamp card are 'J', 'O', and 'I' in the order of the shops visited, the participant receives a gift certificate at the exit. If the types or the order of the stamps are different, no gift certificate is given.

Although it has already been decided which stamp each of the $N$ shops will provide, a new shop is to be opened in the JOI shopping district. We need to decide the location of this new shop and which stamp it will provide. The location for the new shop can be chosen between shop $i$ and shop $i+1$ ($1 \le i \le N-1$), between the entrance and shop $1$, or between shop $N$ and the exit. Also, the stamp for the new shop can be chosen from 'J', 'O', or 'I'.

The shopping district believes that the stamp rally will be more exciting if the number of ways to choose shops to receive a gift certificate is larger. Therefore, we want to find the maximum number of ways to choose the shops to receive a gift certificate when the location and the stamp of the new shop are decided.

Task

Given the information about the stamps provided by the existing shops in the JOI shopping district, write a program to find the maximum number of ways to choose the shops to receive a gift certificate when the location and the stamp of the new shop are decided.

Input

Read the following input from standard input:

• The first line contains an integer $N$, meaning there are currently $N$ shops in the JOI shopping district.
• The second line contains a string $S$ of length $N$ consisting of uppercase English letters 'J', 'O', and 'I'. The $i$-th character from the left of $S$ ($1 \le i \le N$) represents the type of stamp provided by shop $i$.

Output

Output the maximum number of ways to choose the shops to receive a gift certificate in one line to standard output.

Note that the number of ways to choose the shops to receive a gift certificate may not fit in a 32-bit signed integer.

Constraints

All input data satisfies the following conditions:

• $3 \le N \le 100\,000$.

Subtasks

1. (30 points) $N \le 200$ is satisfied.
2. (20 points) $N \le 3\,000$ is satisfied.
3. (50 points) No additional constraints.

Examples

Input 1

5
JOIOI

Output 1

6

In Example 1, when a new shop providing stamp 'J' is opened between shop 1 and shop 2, the stamps provided by the shops in order from the entrance become JJOIOI. In this case, there are 6 ways to choose the shops to receive a gift certificate:

• Visit the 1st, 3rd, and 4th shops.
• Visit the 1st, 3rd, and 6th shops.
• Visit the 1st, 5th, and 6th shops.
• Visit the 2nd, 3rd, and 4th shops.
• Visit the 2nd, 3rd, and 6th shops.
• Visit the 2nd, 5th, and 6th shops.

In Example 1, the number of ways to choose the shops to receive a gift certificate cannot be 7 or more.

Input 2

7
JJJOIII

Output 2

18

Input 3

4
OIIJ

Output 3

2

In Example 3, the number of ways to choose the shops to receive a gift certificate is maximized when a new shop providing stamp 'J' is opened between the entrance and shop 1.